求序列中长度不超过m的最大连续子序列的和

    1. for (int i = 1; i <= n; i++) {
    2.         scanf("%d", &a[i]);
    3.         s[i] = s[i-1]+a[i];
    4.     }
    5.     q.push_back(0);
    6.     for (int i = 1; i <= n; i++) {
    7.         while (q.size() && q.front()<i-m)
    8.             q.pop_front();
    9.         ans = max(ans, s[i]-s[q.front()]);
    10.         while (q.size() && s[q.back()]>=s[i])
    11.             q.pop_back();
    12.         q.push_back(i); 
    13.     }
    14.     cout << ans << "\n";

    在一个序列中找若干段子序列，每一段长度不能超过k，求能满足条件的最大点权和

    1. //f[i]表示从前i个元素中选的最大合法方案数
    2. //状态转移方程f[i] = max(f[i-1], f[i-j+1]+s[i]-s[i-j]) = max(f[i-1],g[i-j]+s[i]); （1<=j<=k）
    3. //定义一个单调递减的队列维护g[i-j]使队头最大，由1<=j<=k可知要求的是长度为k的滑动窗口的最大值。
    4. int g(int i) {
    5.     if (!i)
    6.         return 0;
    7.     return f[i-1]-s[i];
    8. }
    10. cin >> n >> k;
    11.     for (int i = 1; i <= n; i++) {
    12.         scanf("%d", &a[i]);
    13.         s[i] = s[i-1]+a[i];
    14.     }
    15.     deque<int> q;
    16.     q.push_back(0);
    17.     for (int i = 1; i <= n; i++) {
    18.         while (q.size() && q.front()<i-k) 
    19.             q.pop_front();
    20.         f[i] = max(f[i-1], g(q.front())+s[i]);
    21.         while (q.size() && g(q.back())<=g(i))
    22.             q.pop_back();
    23.         q.push_back(i);
    24.     }
    25.     cout << f[n] << "\n";

    在一个序列中找若干个点，任意相邻两点间距离不能大于k，求能满足条件的最小点权和

    1. //f[i]表示在前i个点中选第i个点的小合法方案数
    2. //状态转移方程f[i] = min(f[j])+w[i];  (i-k<=j<=i-1)
    3. //定义一个单调递增队列维护f[j]使队头最小
    5. cin >> n >> k;
    6.     for (int i = 1; i <= n; i++)
    7.         scanf("%d", &a[i]);
    8.     deque<int> q;
    9.     q.push_back(0);
    10.     for (int i = 1; i <= n; i++) {
    11.         if (q.front() < i-k)
    12.             q.pop_front();
    13.         f[i] = f[q.front()]+a[i];
    14.         while (q.size() && f[q.back()] >= f[i])
    15.             q.pop_back();
    16.         q.push_back(i);
    17.     }
    18.     int ans = 0x3f3f3f3f;
    19.     for (int i = n-k+1; i <= n; i++) 
    20.         ans = min(ans, f[i]);
    21.     cout << ans << "\n";

    二维滑动窗口（求大矩阵中固定小矩阵中的最值）

    1. int n, m, k;
    2. int g[N][N];
    3. int row_min[N][N], row_max[N][N]; 
    5. void get_min(int a[], int b[], int tot) {
    6.     deque<int> q;
    7.     q.push_back(0); 
    8.     for (int i = 1; i <= tot; i++) {
    9.         if (q.size() && q.front()<=i-k)
    10.             q.pop_front();
    11.         while (q.size() && a[q.back()]>=a[i])
    12.             q.pop_back();
    13.         q.push_back(i);
    14.         b[i] = a[q.front()]; 
    15.     }
    16. }
    18. void get_max(int a[], int b[], int tot) {
    19.     deque<int> q;
    20.     q.push_back(0); 
    21.     for (int i = 1; i <= tot; i++) {
    22.         if (q.size() && q.front()<=i-k)
    23.             q.pop_front();
    24.         while (q.size() && a[q.back()]<=a[i])
    25.             q.pop_back();
    26.         q.push_back(i);
    27.         b[i] = a[q.front()]; 
    28.     }
    29. }
    31. int main() {
    32.     cin >> n >> m >> k;
    33.     for (int i = 1; i <= n; i++)
    34.         for (int j = 1; j <= m; j++)
    35.             scanf("%d", &g[i][j]);
    36.     for (int i = 1; i <= n; i++) {
    37.         get_min(g[i], row_min[i], m);
    38.         get_max(g[i], row_max[i], m);
    39.     }
    40.     int ans = INF; 
    41.     int a[N], b[N], c[N]; 
    42.     for (int i = k; i <= m; i++) {
    43.         for (int j = 1; j <= n; j++)
    44.             a[j] = row_min[j][i];
    45.         get_min(a, b, n);
    46.         for (int j = 1; j <= n; j++)
    47.             a[j] = row_max[j][i];
    48.         get_max(a, c, n);
    49.         for (int j = k; j <= n; j++)
    50.             ans = min(ans, c[j]-b[j]);
    51.     }
    52.     cout << ans << "\n";
    53.     return 0;
    54. }