题目大意：

你初始时有∞ 元钱，并且每天持有的股票不超过 Maxp 。 有 T 天，你知道每一天的买入价格（ AP[i] ），卖出价格（ Bp[i] ）， 买入数量限制（ AS[i] ），卖出数量限制（ BS[i] ）。 并且两次交易之间必须间隔 W 天。 现在问你 T 天结束后，最大收益是多少。

分析：

注意对题意的理解，虽然有无限的钱，但是买股票是要减少当前的收益的，收益是卖出的总钱数减去买入的钱数。收益并不是只增不减。

可以想到的是：动态规划。设f[i][j]表示前i天之后，剩下j股股票的最大收益。显然根据题意，在j相同的时候，i越往后的时候，f[i][j]越大。

状态转移方程，买入和卖出是相同的思路:

卖出：

f[i][j]=max(f[i-w-1][k]+(k-j)×bp[i]) (j<=k<=j+bs[i])

买入：

f[i][j]=max(f[i-w-1][k]-(j-k)×ap[i]) (j-as[i]<=k<=j)

这种情况的复杂度是O(T×Mp×Mp)直接T掉。

将转移方程括号展开，发现：

f[i-w-1][k]+(k-j)×bp[i]=(f[i-w-1][k]+k×bp[i])-j×bp[i]

在给定i，j的时候，唯一在变的变量就是k，k的取值会影响最大值。而且给予j正确的循环顺序，k的取值区间是逐渐在平移的。

想到了什么？

滑动窗口！单调队列！单调队列优化DP！

我们外层循环i，内层循环j，每次先除去过期的解，加上新的选择，再从单调队列队头取出最优解，进行更新。

注意：

1.在买入和卖出时，为了保证能转移德到j的所有元素都在队列里，j的循环顺序是不同的。

2.对于给定的i，处理买入卖出的顺序可以颠倒。无所谓。

3.当i-w-1小于0时，取0即可。

代码：

#include
     
      using namespace std;const int N=2000+10;int t,mp,w;int f[N][N];int ans;int q[N],hd=1,tl=0;int main(){    scanf("%d%d%d",&t,&mp,&w);    int ap,bp,as,bs;//并不需要数组    memset(f,0xcf,sizeof f);//初值负无穷    f[0][0]=0;    for(int i=1;i<=t;i++)    {        scanf("%d%d%d%d",&ap,&bp,&as,&bs);        hd=1,tl=0;        int from=max(0,i-w-1);//从何转移        for(int j=mp;j>=0;j--)//卖出        {            f[i][j]=max(f[i][j],f[i-1][j]);//可以今天不买不卖            while(hd<=tl&&(j+bs
      
       q[hd])) hd++;            while(hd<=tl&&(f[from][q[tl]]+q[tl]*ap
      
     

总结：

1.对于决策转移时，有明显单调性的情况，对于状态移动时，转移决策重复度较大。都可用单调队列优化。

2.单调队列利用每个元素只能进一次，出一次，使得O(n)变为均摊O(1)复杂度，简化时间。