这道题就是典型的单调队列优化dp了
很明显状态转移的方式有三种
1、前一天不买不卖: dp[i][j]=max(dp[i-1][j],dp[i][j])
2、前i-W-1天买进一些股: dp[i][j]=max(dp[i-W-1][k]-(j-k)*AP[i],dp[i][j])
3、前i-W-1天卖掉一些股: dp[i][j]=max(dp[i-W-1][k]+(k-j)*BP[i],dp[i][j])
第一种转移是o（1）的 第二种如果枚举k时间复杂度接受不了八成是要T的 观察一下后发现 因为一般可以用单调队列优化的DP都能满足形如f[x]=max(min){f[k]}+g[x]
所以我们可以转换一下方程 dp[i][j]=max(dp[i-W-1][k]+k*AP[i])-j*AP[i]。令f[i-W-1][k]=dp[i-W-1][k]+k*AP[i]，则dp[i][j]=max(f[i-W-1][k]) - j*AP[i]。
这样之后就可以用单调队列优化了呀。
注意买的j要从0~mxa而卖的应该是mxa~0 虽然都是这是因为买的时候是k+as【i】 而卖的时候是k-bs【i】的原因 其余的看代码咯
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int M=2007,inf=0x3f3f3f3f; int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();} return ans*f; } struct node{int pos,f;}e[M]; int n,mxa,w,ans,head,tail; int ap[M],bp[M],as[M],bs[M],dp[M][M]; int main() { n=read(); mxa=read(); w=read(); for(int i=1;i<=n;i++) ap[i]=read(),bp[i]=read(),as[i]=read(),bs[i]=read(); for(int i=0;i<=n;i++) for(int j=0;j<=mxa;j++) dp[i][j]=-inf; for(int i=1;i<=w+1;i++) for(int j=0;j<=min(mxa,as[i]);j++) dp[i][j]=-ap[i]*j; dp[0][0]=0; for(int i=1;i<=n;i++){ for(int j=0;j<=mxa;j++) dp[i][j]=max(dp[i-1][j],dp[i][j]); if(i<=w+1) continue; int now=i-w-1; head=0; tail=0; for(int j=0;j<=mxa;j++){ int nowf=dp[now][j]+j*ap[i]; while(head<tail&&nowf>e[tail-1].f) tail--; e[tail].f=nowf; e[tail++].pos=j; while(head<tail&&e[head].pos+as[i]<j) head++; dp[i][j]=max(dp[i][j],e[head].f-j*ap[i]); } head=0; tail=0; for(int j=mxa;j>=0;j--){ int nowf=dp[now][j]+j*bp[i]; while(head<tail&&nowf>e[tail-1].f) tail--; e[tail].f=nowf; e[tail++].pos=j; while(head<tail&&e[head].pos-bs[i]>j) head++; dp[i][j]=max(dp[i][j],e[head].f-j*bp[i]); } } printf("%d ",dp[n][0]); return 0; }
最后强调一下 别的题解最后的答案有的是从dp【n】【0~mxa】或者是dp【0~n】【0】里面寻找答案但是我觉得如果最佳答案早dp【n】【0~mxa】里那肯定是手里没有持有股票都卖掉了才赚好吧所以答案肯定是dp【n】【0】 如果答案在dp【0~n】【0】那任意的最优解肯定能通过不买不卖的方式转移到dp【n】【0】所以答案就是dp【n】【0】了啦