代码基本是跟着yy dalao码的吧，
主要是要知道单调队列优化要怎么做，
f[i][j]表示第i天手里有j股时的收益。
从第一天到第w+1天初始化为-e[i].ap*j（因为此时只能买不能卖），其余为-inf。
分三种情况：
1.不买不卖：即f[i][j]=max(f[i][j],f[i-1][j]);
2.买进： f[i][j]=max(f[i-W-1][k]-(j-k)*e[i].ap,f[i][j])。在这里j-e[i].as<k<=mxa，利用f[i][j]=max(f[i-W-1][k]+k*e[i).ap-j*e[i].ap。令a[i-W-1][k]=f[i-W-1][k]+k*e[i].ap(事实上完全不用a这个数组，用单调队列），则f[i][j]=max(a[i-W-1][k]) - j*e[i].ap。枚举要从0到mxa。
3.卖出，原理同上，枚举要从mxa到0。
最后的f[n][0]即为答案（现实意义为第n天此时手里没有任何股票时的最大收益）。
具体实现看代码：
#include<cstdio> #include<cstring> #include<iostream> const int M=2010,inf=0x3f3f3f3f; using namespace std; struct point { int ap,bp,as,bs; }e[M]; struct node{int pos,k;}a[M]; int f[M][M],head,tail; int main() { int n,mxa,w; bool ok; memset(f,-inf,sizeof(f)); scanf("%d %d %d",&n,&mxa,&w); for(int i=1;i<=n;i++)scanf("%d %d %d %d",&e[i].ap,&e[i].bp,&e[i].as,&e[i].bs); for(int i=1;i<=w+1;i++) for(int j=1;j<=e[i].as;j++) f[i][j]=-e[i].ap*j; f[0][0]=0; for(int i=1;i<=n;i++) { for(int j=0;j<=mxa;j++)f[i][j]=max(f[i][j],f[i-1][j]); if(i<=w+1)continue; int now=i-w-1; head=tail=0; for(int j=0;j<=mxa;j++) { ok=true; int now1=f[now][j]+j*e[i].ap; while(head<tail&&a[tail-1].k<now1)tail--; a[tail].k=now1;a[tail++].pos=j; while(a[head].pos+e[i].as<j){if(head==tail){ok=false;break;}head++;} if(ok)f[i][j]=max(f[i][j],a[head].k-j*e[i].ap); } head=tail=0; for(int j=mxa;j>=0;j--) { ok=true; int now1=f[now][j]+j*e[i].bp; while(head<tail&&a[tail-1].k<now1)tail--; a[tail].k=now1;a[tail++].pos=j; while(a[head].pos-e[i].bs>j){if(head==tail){ok=false;break;}head++;} if(ok)f[i][j]=max(f[i][j],a[head].k-j*e[i].bp); } } printf("%d",f[n][0]); return 0; }
注意一点就是hdu3401这道题有多组数据，记得改一下再交啊（不然就像我一样WA了……）
#include<cstdio> #include<cstring> #include<iostream> const int M=2010,inf=0x3f3f3f3f; using namespace std; struct point { int ap,bp,as,bs; }e[M]; struct node{int pos,k;}a[M]; int f[M][M],head,tail; int main() { int n,mxa,w,tt; bool ok; scanf("%d",&tt); while(tt--) { memset(f,-inf,sizeof(f)); scanf("%d %d %d",&n,&mxa,&w); for(int i=1;i<=n;i++)scanf("%d %d %d %d",&e[i].ap,&e[i].bp,&e[i].as,&e[i].bs); for(int i=1;i<=w+1;i++) for(int j=1;j<=e[i].as;j++) f[i][j]=-e[i].ap*j; f[0][0]=0; for(int i=1;i<=n;i++) { for(int j=0;j<=mxa;j++)f[i][j]=max(f[i][j],f[i-1][j]); if(i<=w+1)continue; int now=i-w-1; head=tail=0; for(int j=0;j<=mxa;j++) { ok=true; int now1=f[now][j]+j*e[i].ap; while(head<tail&&a[tail-1].k<now1)tail--; a[tail].k=now1;a[tail++].pos=j; while(a[head].pos+e[i].as<j){if(head==tail){ok=false;break;}head++;} if(ok)f[i][j]=max(f[i][j],a[head].k-j*e[i].ap); } head=tail=0; for(int j=mxa;j>=0;j--) { ok=true; int now1=f[now][j]+j*e[i].bp; while(head<tail&&a[tail-1].k<now1)tail--; a[tail].k=now1;a[tail++].pos=j; while(a[head].pos-e[i].bs>j){if(head==tail){ok=false;break;}head++;} if(ok)f[i][j]=max(f[i][j],a[head].k-j*e[i].bp); } } printf("%d ",f[n][0]); } return 0; }