传送门
单调队列优化 d p dp dp
这位大佬的题解写得非常清楚
1.凭空买,只要考虑买的最大值
2.不买也不卖,直接由上一天转移
3.在之前的基础上买股票
4.在之前的基础上卖股票
#include<bits/stdc++.h>
#define max(a,b) ((a)>(b))?(a):(b)
using namespace std;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){int x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=(x+(x<<2)<<1)+c-48;return x*f;
}
int n,m,ap,bp,as,bs,w,f[2005][2005],q[2005],h,t;
int main(){n=read(),m=read(),w=read();memset(f,128,sizeof(f));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;h=1,t=0;for(int j=0;j<=m;++j){while(h<=t&&q[h]<j-as) ++h;while(h<=t&&f[i-w-1][q[t]]+q[t]*ap<=f[i-w-1][j]+j*ap) --t;q[++t]=j;if(h<=t) f[i][j]=max(f[i][j],f[i-w-1][q[h]]+q[h]*ap-j*ap);}h=1,t=0;for(int j=m;j>=0;--j){while(h<=t&&q[h]>j+bs) ++h;while(h<=t&&f[i-w-1][q[t]]+q[t]*bp<=f[i-w-1][j]+j*bp) --t;q[++t]=j;if(h<=t) f[i][j]=max(f[i][j],f[i-w-1][q[h]]+q[h]*bp-j*bp);}}return !printf("%d",f[n][0]);
}