题目链接：点击打开链接
【题解】
大致题意：有人发现了股票的规律，现在抱着多赚钱的想法，想在t天后获得最大收益，现已知他任意时刻手里只能持有maxp份股票，而且每股股票买了后w+1天才可以再次交易（继续卖或者买或者不动），不仅如此，已知每天每股股票买入价是buy[i],卖出价是sell[i],每天的买入数最多spa[i]，卖出最多spb[i]。 求t天后的最大收益。
分析：
初一看题目很复杂，条件限制很多，不要慌，慢慢梳理。
用数组dp[i][j]表示第 i 天持有 j 股股票的最大收益。
那么总共可以分三种情况:
1)不买不卖 dp[i][j] = max(dp[i][j],dp[i-1][j]);
2)买了股票 dp[i][j] = max(dp[i][j],dp[i-W-1][k] - (j - k) * AP[i]);
3)卖了股票 dp[i][j] = max(dp[i][j],dp[i-W-1][k] + (k - j) * BP[i]);
如果用普通的枚举法算，复杂度是立方级的，所以要优化。
买票的转移方程转化一下就是dp[i][j]=max(dp[i][j] , dp[i-W-1][k]+k*AP[i]-j*AP[i] ;
令f[i-W-1] = dp[i-W-1][k] + k * AP[i];
那么dp[i][j] = max(f[i-W-1]) - j * AP[i];对于f[i-W-1]可以用单调队列来求。这样复杂度就成了n ^ 2。买股票的也类似。
【AC代码】
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
const int N=2005;
const int inf=1e9;
int m,maxp,W,T,spa[N],spb[N];
int buy[N],sell[N];
int dp[2002][2002];struct node
{int x;int pos;
}ss[N];int head,tail;int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d%d",&T,&maxp,&W);for(int i=1;i<=T;++i)scanf("%d%d%d%d",&buy[i],&sell[i],&spa[i],&spb[i]);for(int i=0;i<=T;++i)for(int j=0;j<=maxp;++j)dp[i][j]=-inf;for(int i=1;i<=W+1;++i)for(int j=0;j<=min(maxp,spa[i]);++j)dp[i][j]=-buy[i]*j; //特殊处理dp[0][0]=0;for(int i=1;i<=T;++i){for(int j=0;j<=maxp;++j) //不买不卖dp[i][j]=max(dp[i][j],dp[i-1][j]);if(i<=W+1) continue;//还不到w+1天 ，不能买int pre=i-W-1;// w+1 天后head=tail=0; //单调队列for(int j=0;j<=maxp;++j)// 遍历手中的股票数 {int newx=dp[pre][j]+j*buy[i];//i-W-1天前j股可以赚的钱+买j股票花的钱while(head<tail && ss[tail-1].x<newx) tail--;ss[tail].x=newx;ss[tail++].pos=j;while(head<tail && ss[head].pos+spa[i]<j) head++;dp[i][j]=max(dp[i][j],ss[head].x-j*buy[i]);}head=tail=0; //同上for(int j=maxp;j>=0;--j){int newx=dp[pre][j]+j*sell[i];while(head<tail && ss[tail-1].x<newx) tail--;ss[tail].x=newx;ss[tail++].pos=j;while(head<tail&& ss[head].pos-spb[i]>j) head++;dp[i][j]=max(dp[i][j],ss[head].x-j*sell[i]);}}int ans=0;for(int i=0;i<=maxp;++i) //遍历 寻找第T天手中有i股股票时的最大收益ans=max(ans,dp[T][i]);printf("%d\n",ans);}return 0;
}