题目链接：hdu 3401 Trade
题解转自
题意：
知道之后n天的股票买卖价格（api，bpi），以及每天股票买卖数量上限（asi，bsi），问他最多能赚多少钱。开始时有无限本金，要求任两次交易需要间隔W天以上，即第i天交易，第i+w+1天才能再交易。同时他任意时刻最多只能拥有maxp的股票，
题解：
容易写出DP方程 dp[i][j]=max{dp[i-1][j],max{dp[r][k]-APi[i]*(j-k)}(0<r<i-w,k<j),max{dp[r][k]+BPi[i]*(k-j)}(0<r<i-w,k>j)} 分别是第i天不交易，买股票和卖股票3种转移。
第一眼看会发现这个方程十分冗杂，没有下手的地方。我们可以分析下，对于买卖股票的转移中的dp[r][k]中的r是否有枚举的价值，注意dp[i][j]中取最大时会考虑dp[i-1][j]的值，也就是dp[i-w-1][k]>=dp[r][k](0<r<i-w)恒成立。这样就省去了r 的枚举，但这还不够。以买股票为例，我们可以化简max{dp[i-w-1][k]-APi[i]*(j-k)}(k<j)}，即dp[i-w-1][k]-APi[i]*(j-k)=dp[i-w-1][k]+APi[i]*k-APi[i]*j（k<j），可以发现对于确定的i和j只要取符合条件中最大的dp[i-w-1][k]+APi[i]*k即可，这个可以通过单调队列实现。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 5 const int N=2007,inf=1<<30; 6 int _,t,p,w,dp[N][N],ap[N],bp[N],as[N],bs[N],head,tail; 7 8 struct node{int x,p;}Q[N],tmp; 9 10 inline void up(int &a,int b){if(a<b)a=b;} 11 12 int main() 13 { 14 scanf("%d",&_); 15 while(_--) 16 { 17 scanf("%d%d%d",&t,&p,&w); 18 F(i,1,t)scanf("%d%d%d%d",ap+i,bp+i,as+i,bs+i); 19 F(i,0,t)F(j,0,p)dp[i][j]=-inf; 20 F(i,1,w+1)F(j,0,as[i])dp[i][j]=-ap[i]*j; 21 F(i,2,t) 22 { 23 F(j,0,p)up(dp[i][j],dp[i-1][j]);//不操作 24 if(i<=w+1)continue; 25 head=1,tail=0; 26 F(j,0,p)//买 27 { 28 tmp.p=j,tmp.x=dp[i-w-1][j]+ap[i]*j; 29 while(head<=tail&&tmp.x>Q[tail].x)tail--; 30 Q[++tail]=tmp; 31 while(head<=tail&&Q[head].p+as[i]<j)head++; 32 up(dp[i][j],Q[head].x-ap[i]*j); 33 } 34 head=1,tail=0; 35 for(int j=p;j>=0;j--)//卖 36 { 37 tmp.p=j,tmp.x=dp[i-w-1][j]+bp[i]*j; 38 while(head<=tail&&tmp.x>Q[tail].x)tail--; 39 Q[++tail]=tmp; 40 while(head<=tail&&Q[head].p-bs[i]>j)head++; 41 up(dp[i][j],Q[head].x-bp[i]*j); 42 } 43 } 44 int ans=0; 45 F(i,0,p)up(ans,dp[t][i]); 46 printf("%d ",ans); 47 } 48 return 0; 49 }