题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3401
题目大意：现在要你去炒股，给你每天的开盘价值，每股买入价值为ap，卖出价值为bp，每天最多买as股，最多卖出bs股，并且要求两次买卖必须间隔W天，问你在T天内如何进行炒股操作从而获得最大收益。
解题思路：先吐槽一下，会单调队列但不会dp不行，会dp但不会单调队列也不行！！开始dp动态转移方程倒是写对了，然后算算时间复杂度T*T*Maxp*Maxp，优化不得当，一直以为是dp思路错了，囧。
对于有单调队列参与dp的题，dp方程必须准确先写好，然后再观察可否用单调队列。
dp[i][j]：表示第i天手上持有j股的最大利益。三种决策：
{ -------1、不买不卖 dp[i-1][j]
dp[i][j]=max { -------2、买 dp[r][k]-ap[i]*(j-k) (j>=k，r<=i-w-1)
{ -------3、卖 dp[r][k]+bp[i]*(k-j) (j<=k，r<=i-w-1)
由dp方程可知时间复杂度为T*T*Maxp*Maxp,其实仔细观察可以看出，r其实就等于i-w-1（联系决策1想想为什么），时间复杂度降低一维。
看第二个dp转移方程，dp[i][j]=max(dp[i][j],dp[i-w-1][k]-ap[i]*(j-k)).
dp[i-w-1][k]-ap[i]*(j-k)=(dp[i-w-1][k]+ap[i]*k)-ap[i]*j , 在j固定的情况下（dp[i][j]固定），k变式子值变，我们只需保存变化过程中的最大值即可，很容易想到单调队列。决策三亦是如此。因为要保存最大值，所以买是j从0开始和卖是j从Maxp开始，最大值优先。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std; const int maxn=;
const int oo=0x3fffffff;
int ap[maxn], bp[maxn], as[maxn], bs[maxn];
int dp[maxn][maxn];
int W, T, Maxp, n; struct node
{
int num, val;
}que[maxn]; int main()
{
cin >> T;
while(T--)
{
cin >> n >> Maxp >> W;
for(int i=; i<=n; i++)
for(int j=; j<=Maxp; j++) dp[i][j]=-oo;
for(int i=; i<=n; i++) scanf("%d%d%d%d",ap+i,bp+i,as+i,bs+i);
for(int i=; i<=n; i++) dp[i][]=;
for(int i=; i<=W+; i++)
for(int j=; j<=as[i]; j++) dp[i][j]=-j*ap[i];
for(int j=; j<=Maxp; j++)
for(int i=; i<=W+; i++)
dp[i][j]=max(dp[i][j],dp[i-][j]);
for(int i=W+; i<=n; i++)
{
int front=, tail=-;
for(int j=; j<=Maxp; j++)
{
dp[i][j]=max(dp[i][j],dp[i-][j]);
while(front<=tail&&que[tail].val<=dp[i-W-][j]+ap[i]*j) tail--;
que[++tail].val=dp[i-W-][j]+ap[i]*j, que[tail].num=j;
while(front<=tail&&j-que[front].num>as[i]) front++;
dp[i][j]=max(dp[i][j],que[front].val-ap[i]*j);
}
front=, tail=-;
for(int j=Maxp; j>=; j--)
{
while(front<=tail&&que[tail].val<=dp[i-W-][j]+bp[i]*j) tail--;
que[++tail].val=dp[i-W-][j]+bp[i]*j, que[tail].num=j;
while(front<=tail&&que[front].num-j>bs[i]) front++;
dp[i][j]=max(dp[i][j],que[front].val-bp[i]*j);
}
}
int maxx=;
for(int i=; i<=Maxp; i++)
maxx=max(maxx,dp[n][i]);
printf("%d\n",maxx);
}
return ;
}