单调队列优化dp

一题思维好题

就是有3个转移方程

$f_{i,j}=max(f_{i,j},f_{i-1,j})$ $(0\leq j\leq m)$

$f_{i,j}=max(f_{i,j},f_{i-w-1,k}+k*ap_i)-j*ap_i$ $(j-as_i\leq k<j)$

$f_{i,j}=max(f_{i,j},f_{i-w-1,k}+k*bp_i)-j*bp_i$ $(j<k\leq j+bs_i)$

初始化:$f_{i,j}=-ap_i*j ​$ $(0\leq j\leq as_i)​$

容易观察到第二个和第三个可以用单调队列优化

于是就做完了

#include <bits/stdc++.h>
#define il inline
#define Max 2005
using namespace std;
il int read()
{
    char c=getchar();
    int x=0,f=1;
    while(c>'9'||c<'0')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m,w;
int f[Max][Max],ap,bp,as,bs,q[Max],ans;
int main()
{
    memset(f,128,sizeof(f));
    n=read(),m=read(),w=read();
    for(int i=1;i<=n;i++)
    {
        ap=read(),bp=read(),as=read(),bs=read();
        for(int j=0;j<=as;j++)
            f[i][j]=-1*(j)*ap;
        for(int j=0;j<=m;j++)
            f[i][j]=max(f[i][j],f[i-1][j]);
        if(i<=w) continue;
        int l=1,r=0;
        for(int j=0;j<=m;j++)
        {
            while(l<=r&&q[l]<j-as) l++;
            while(l<=r&&f[i-w-1][q[r]]+q[r]*ap<=f[i-w-1][j]+j*ap) r--;
            q[++r]=j;
            if(l<=r) f[i][j]=max(f[i][j],f[i-w-1][q[l]]+q[l]*ap-j*ap);
        }
        l=1,r=0;
        for(int j=m;j>=0;j--)
        {
            while(l<=r&&q[l]>j+bs) l++;
            while(l<=r&&f[i-w-1][q[r]]+q[r]*bp<=f[i-w-1][j]+j*bp) r--;
            q[++r]=j;
            if(l<=r) f[i][j]=max(f[i][j],f[i-w-1][q[l]]+q[l]*bp-j*bp);
        }
    }
    for(int i=0;i<=m;i++) ans=max(ans,f[n][i]);
    cout<<ans<<endl;
}