单调队列原理回顾和例题分析

原理例题优化DP

单调队列解决的问题的基本模型是滑动窗口问题，也就是给一个数组和一个窗口大小，从左面滑到最右面，问每次滑动的区间最大值和最小值

这里只用语言简单描述一下，具体画图可以参考https://zhuanlan.zhihu.com/p/346354943如果是维护区间最大值，用一个双端队列，我们的目的是让队尾元素为区间最大值，每次入队的时候把所有队首元素比当前还小的全部弹出，然后把这个元素放在队首，同时检查队尾元素是否已经超出了窗口，如果超出了窗口，那么全部弹出，最后得到队尾元素就是区间最大值，这也就是所谓的如果有一个人比你还大比你还弱，那么那个人就可以退役了，如果维护区间最小值同理 例题

https://www.luogu.com.cn/problem/P1886

滑动窗口求区间最大值和最小值

#include 

using namespace std;

typedef long long ll;

struct st{
    int id;
    int val;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector a(n);
    for(int i=0;i> a[i].val;
        a[i].id = i;
    }
    deque q;
    for(int i=0;i= a[i].val) q.pop_front();
        q.push_front(a[i].id);
        while(a[q.back()].id <= (i - k)) q.pop_back();
        if(i >= k - 1) cout << a[q.back()].val << ' ';
    }
    cout << 'n';
    q.resize(0);
    for(int i=0;i= k - 1) cout << a[q.back()].val << ' ';
    }
    return 0;
}

https://www.luogu.com.cn/problem/P2216
在一个大区域中求一个子区域，使得这个子区域中的最大值和最小值的差最小，求这个值

从行来看，一个固定大小的子区域相当于一个滑动窗口，我们可以横向求出滑动窗口内部的最小值和最大值这样以后，我么按照列方向对行方向求出的矩阵再做两次滑动窗口，得到的答案就是一个区域的最大值和最小值，不难理解

#include 

using namespace std;

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int a, b, n;
    cin >> a >> b >> n;
    vector > mp(a, vector(b));

    vector > mxx(a, vector(b));
    vector > mxy(a, vector(b));
    vector > mnx(a, vector(b));
    vector > mny(a, vector(b));
    for(int i=0;i> mp[i][j];
        }
    }
    vector S(max(a, b));
    for(int i=0;i q1, q2;
        for(int j=0;j mp[i][q1.front()]){
                q1.pop_front();
            }
            q1.push_front(j);
            while(j - q1.back() >= n) q1.pop_back();
            if(j >= n - 1) mxx[i][j] = mp[i][q1.back()];

            while(!q2.empty() && mp[i][j] < mp[i][q2.front()]){
                q2.pop_front();
            }
            q2.push_front(j);
            while(j - q2.back() >= n) q2.pop_back();
            if(j >= n - 1) mnx[i][j] = mp[i][q2.back()];
        }
    }

    for(int j=0;j q1, q2;
        for(int i=0;i mxx[q1.front()][j]){
                q1.pop_front();
            }
            q1.push_front(i);
            while(i - q1.back() >= n) q1.pop_back();
            if(i >= n - 1) mxy[i][j] = mxx[q1.back()][j];

            while(!q2.empty() && mnx[i][j] < mnx[q2.front()][j]){
                q2.pop_front();
            }
            q2.push_front(i);
            while(i - q2.back() >= n) q2.pop_back();
            if(i >= n - 1) mny[i][j] = mnx[q2.back()][j];
        }
    }
    int ans = 0x7fffffff;
    for(int i=n-1;i 
优化DP 
https://www.luogu.com.cn/problem/P2034
 
用
     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         i
        
        
         ]
        
        
         [
        
        
         0
        
        
         /
        
        
         1
        
        
         ]
        
       
       
        dp[i][0/1]
       
      
     dp[i][0/1]表示第
     
      
       
        
         i
        
       
       
        i
       
      
     i个物品选或者不选所能达到的数字之和的最大值，
     
      
       
        
         s
        
        
         u
        
        
         m
        
        
         [
        
        
         i
        
        
         ]
        
       
       
        sum[i]
       
      
     sum[i]表示前缀和，因为不能有超过
     
      
       
        
         k
        
       
       
        k
       
      
     k个连续的数字被选择，所以转移方程显然为
      
       
        
         
          {
         
         
          
           
            
             
              
               d
              
              
               p
              
              
               [
              
              
               i
              
              
               ]
              
              
               [
              
              
               0
              
              
               ]
              
             
            
           
           
            
             
              
              
               =
              
              
               m
              
              
               a
              
              
               x
              
              
               (
              
              
               d
              
              
               p
              
              
               [
              
              
               i
              
              
               −
              
              
               1
              
              
               ]
              
              
               [
              
              
               0
              
              
               ]
              
              
               ,
              
              
               d
              
              
               p
              
              
               [
              
              
               i
              
              
               −
              
              
               1
              
              
               ]
              
              
               [
              
              
               1
              
              
               ]
              
             
            
           
          
          
           
            
             
              
               d
              
              
               p
              
              
               [
              
              
               i
              
              
               ]
              
              
               [
              
              
               1
              
              
               ]
              
             
            
           
           
            
             
              
              
               =
              
              
               m
              
              
               a
              
              
               x
              
              
               (
              
              
               d
              
              
               p
              
              
               [
              
              
               i
              
              
               ]
              
              
               [
              
              
               1
              
              
               ]
              
              
               ,
              
              
               d
              
              
               p
              
              
               [
              
              
               j
              
              
               ]
              
              
               [
              
              
               0
              
              
               ]
              
              
               +
              
              
               s
              
              
               u
              
              
               m
              
              
               [
              
              
               i
              
              
               ]
              
              
               −
              
              
               s
              
              
               u
              
              
               m
              
              
               [
              
              
               j
              
              
               ]
              
              
               )
              
              
               ,
              
              
               i
              
              
               −
              
              
               k
              
              
               ≤
              
              
               j
              
              
               ≤
              
              
               i
              
             
            
           
          
         
        
        
          left{ begin{aligned} dp[i][0] & =max(dp[i-1][0],dp[i-1][1]\ dp[i][1] & =max(dp[i][1],dp[j][0]+sum[i]-sum[j]),i-kleq jleq i end{aligned} right.
        
       
      {dp[i][0]dp[i][1]​=max(dp[i−1][0],dp[i−1][1]=max(dp[i][1],dp[j][0]+sum[i]−sum[j]),i−k≤j≤i​
 但这样第二行的时间复杂度是
     
      
       
        
         O
        
        
         (
        
        
         
          n
         
         
          2
         
        
        
         )
        
       
       
        O(n^2)
       
      
     O(n2)，考虑优化，因为
     
      
       
        
         i
        
        
         −
        
        
         k
        
        
         ≤
        
        
         j
        
        
         ≤
        
        
         i
        
       
       
        i-kleq jleq i
       
      
     i−k≤j≤i，我们只需要找到使得
     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         j
        
        
         ]
        
        
         [
        
        
         0
        
        
         ]
        
        
         −
        
        
         s
        
        
         u
        
        
         m
        
        
         [
        
        
         j
        
        
         ]
        
       
       
        dp[j][0]-sum[j]
       
      
     dp[j][0]−sum[j]最大的情况即可，使用单调队列维护它的最大值，使之处于队首，队列内部元素的
     
      
       
        
         d
        
        
         p
        
        
         [
        
        
         j
        
        
         ]
        
        
         [
        
        
         0
        
        
         ]
        
        
         −
        
        
         s
        
        
         u
        
        
         m
        
        
         [
        
        
         j
        
        
         ]
        
       
       
        dp[j][0]-sum[j]
       
      
     dp[j][0]−sum[j]是单调递减的 
#include 

using namespace std;

typedef long long ll;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector a(n + 1), sum(n + 1);
    for(int i=1;i<=n;i++){
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    vector > dp(n + 1, vector(2));
    deque q;
    q.push_back(0);
    for(int i=1;i<=n;i++){
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
        while(!q.empty() && i - k > q.front()) q.pop_front();
        dp[i][1] = dp[q.front()][0] - sum[q.front()] + sum[i];
        while(!q.empty() && sum[i] - dp[i][0] < sum[q.back()] - dp[q.back()][0]) q.pop_back();
        q.push_back(i);
    }
    cout << max(dp[n][0], dp[n][1]);
    return 0;
}