题目地址；http://acm.uestc.edu.cn/problem.php?pid=1696&cid=167
状态定义：dp[i][j]表示第 i 天，手持 j 股时最多能赚多少钱。
状态转移：第i天交易的状态只能由[0, i-w-1]天的状态转移过来！！！处理方法：构造a[]数组，a[j]表示第[0, i-w-1]天中，手持j股的最大收益，在转移第w+1天到最后一天时，每转移完一天后，更新a[]数组。第i天的状态dp[i][j]的转移根据a[]数组来，而不是dp[i-1][]（其实你会发现第i天时，a[j]就是dp[i-w-1][j]）。
优化：单调队列。
详细细节见代码的注释哟！
#include<cstdio> #include<cstring> #include<cstdlib> #include<string> #include<cmath> #include<iostream> #include<algorithm> #include<map> #include<vector> //#include<queue> #define sf scanf #define pf printf #define pfn printf("\n"); #define ll long long #define INF 0x7fffffff using namespace std; int t,mp,w,dp[2000][2000],a[2000],deque1[2000],deque2[2000],front1,rear1,front2,rear2; int s[2000],b[2000],sp[2000],bp[2000],ans; int max3(int x1,int x2,int x3){ if(x1<x2) x1=x2; if(x1<x3) x1=x3; return x1; } void ini(){ for(int i=0; i<=t; i++) for(int j=0; j<=mp+1; j++) dp[i][j] = -INF; //-INF表示未定义 } void DP(){ //先定义4个变量，后面会解释作用。。 int toplimit,t1,t2,t3; //construct the initial state，前w天内只能买入或什么不做，没的卖。 for(int i=1; i<=w; i++){ for(int j=0; j<=mp; j++){ //最多手持mp股哟 if(j<=b[i]) //最多买b[i]股哟 dp[i][j] = -bp[i]*j; if(dp[i][j]<dp[i-1][j]) dp[i][j]=dp[i-1][j]; //如果前一天值更大，说明吴神在[1,i-1]天中可以以更低价格买到j股 } } //a[]数组是个很重要的数组，这里做个说明： //1. a[]数组会在处理完一天后更新一次（第w+1天至第t天）； //2. 处理第i天时，a[j]表示第1天到第i-w天内（即第i天交易的上一次可能交易时间），手持j股时的最大收益。 //3. 每处理完一天，a[]数组根据第i+1-w天更新。 for(int j=0; j<=mp; j++) //初始化a[]数组 a[j]=dp[1][j]; //state trans for(int i=w+1; i<=t; i++){ //construct the deque2，构造单调队列只是为了优化 //deque2是这一次交易，要卖出股票的情况。 front1=rear1=front2=rear2=0; toplimit=min(mp,s[i]); for(int j=1; j<=toplimit; j++){ if(a[j]==-INF) continue; while(rear2>front2 && a[j]+(j-deque2[rear2-1])*sp[i] >= a[deque2[rear2-1]]) rear2--; deque2[rear2++]=j; } //第i天手持j股的最大收益就是按下面转移来的 for(int j=0; j<=mp; j++){ //t1表示这次是卖出，卖出后的最大收益 //t2表示这次是买入，买入后的最大收益 //t3表示这次什么也不做的最大收益 t1=t2=t3=-INF; if(rear1>front1) t1 = a[deque1[front1]] - (j-deque1[front1])*bp[i]; if(rear2>front2) t2 = a[deque2[front2]] + (deque2[front2]-j)*sp[i]; t3=dp[i-1][j]; dp[i][j] = max3(t1,t2,t3); //更新单调队列deque1 if(s[i]>0 && rear2>front2 && deque2[front2]==j+1) front2++; if(s[i]>0 && j+s[i]+1<=mp && a[j+s[i]+1] != -INF){ while(rear2>front2 && a[j+s[i]+1]+(j+s[i]+1-deque2[rear2-1])*sp[i] >= a[deque2[rear2-1]]) rear2--; deque2[rear2++]=j+s[i]+1; } //更新另外一个单调队列deque2，表示这次交易要买入股票的情况 if(b[i]>0 && rear1>front1 && deque1[front1]==j-b[i]) front1++; if(b[i]>0 && a[j] != -INF){ while(rear1>front1 && a[j]+(j-deque1[rear1-1])*bp[i] >= a[deque1[rear1-1]]) rear1--; deque1[rear1++]=j; } } //update array a[] for(int j=0; j<=mp; j++) a[j]=dp[i-w+1][j]; } } int main() { int T; cin>>T; while(T--){ sf("%d %d %d",&t,&mp,&w); for(int i=1; i<=t; i++){ sf("%d %d %d %d",&s[i],&b[i],&sp[i],&bp[i]); } //特判一下，只有0天或只能手持0股，吴神还能做什么呢？ if(t==0 || mp==0){ ans=0; cout<<ans<<endl; continue; } //第i天交易后，只能在第i+w+1天再交易，现在将w++，于是第i天后，第i+w天才能交易。 w++; //if(w==0) w=1; ini(); //dp[i][j]表示第i天，手持j股时最多能赚多少钱。 DP(); ans=-INF; //对第t天（最后一天）的结果，找最大值。that's it!!! for(int j=0; j<=mp; j++) if(dp[t][j]>ans) ans=dp[t][j]; if(ans<0) ans=0; pf("%d",ans); pfn } return 0; }