单调队列优化DP

AcWing 135. 最大子序和

题目链接：https://www.acwing.com/problem/content/137/

思路

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 3e5 + 10;
int a[N];
int n, m;
int q[N];
int ans;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i], a[i] += a[i - 1];

    int hh = 0, tt = 0;
    q[0] = 0, ans=a[1];
    for(int i=1;i<=n;i++)
    {
        if(hh<=tt && q[hh]<i-m) hh++;//q[h]不在窗口[i-m,i-1]内，队头出列
        ans=max(ans,a[i]-a[q[hh]]);//使用队头的最小值更新答案
        while(hh<=tt && a[i]<=a[q[tt]]) tt--;//当前值<=队尾值，让队尾出队，保证这个窗口是单调递增的
        q[++tt]=i;//把下标入队，便于队头出列
    }
    cout<<ans<<endl;
    return 0;
}

AcWing 1087. 修剪草坪

题目链接：https://www.acwing.com/problem/content/1089/

代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n, m;
LL s[N];
LL f[N];
int q[N];

LL g(int i)
{
    if (!i) return 0;
    return f[i - 1] - s[i];
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }

    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (q[hh] < i - m) hh ++ ;
        f[i] = max(f[i - 1], g(q[hh]) + s[i]);
        while (hh <= tt && g(q[tt]) <= g(i)) tt -- ;
        q[ ++ tt] = i;
    }

    printf("%lld\n", f[n]);

    return 0;
}