严重鄙视这一题，弄了N复杂的一个题意。。。做了好多天都没想法，今天终于看着题解把它A掉了。。
其实单调队列如果再没有明显的 max(i,i+K) 的情况下。。很难想得到。这个题目就是。
题意是说一个人跟政府关系很好。知道了下面T天每天的股票价格。但是XX告诉他，儿子啊，我告诉你啊，你买股票要这么买，要不会被抓的。你手上的股票数最多不能超过maxP,而且某一天买卖之后，下次买卖的时间必须延后W天，你懂的。好了，下面告诉你T天的价格，你自己赚钱去吧。
这题的朴素的DP方程是这样的: res[i][j] = res[i-W-1][k] + 买入或卖出的代价 ( j-ASi<=k <=j+BSi )
有人会问为什么只枚举了i-W-1天呢？前面的日子呢？额。。。前面的日子已经归到i-W-1天啦。
好了，这破题。状态复杂度: T*maxP,决策复杂度maxP。无悬念的超时了。
别人说用单调队列优化就单调队列优化吧。
我们可以这样想：假如i-w-1天那家伙持有的股票根据那天股票的价格换成了钱，就是都虚拟换成r[i-w-1][0]，这样，我们可以知道，我们不会选择钱少的决策的，因为我们现在得j是固定的，当换算后的钱多的时候，无论怎样决策都比钱少的好。。，好了，着就变成了第二句话那样的模型了，直接换算出来，弄个丑陋的单调队列出来，然后唧唧歪哇一大堆。
下面是代码，写的比较长，比较乱。纠结。。。。纠结。。。。
//单调队列用法：求一段序列里的最值。 加上决策有序
//这个题 ： 决策的时候，把持有的股票数转化出来，可知当决策为 max(res[i-W-1][j-ASi],res[i-W-1][j+BSi]+k*BAi,BPi)时，
#include <stdio.h>
#include <string.h>
#define inf 900000
typedef struct
{
int APi,BPi,ASi,BSi;
}node;
typedef struct
{
int pos;
int res;
}qe;
int qhead,qtail;
qe queue[410010];
node data[2010];
int res[2010][2010];//第i天拥有j的股票赚的最多的钱
int T,W,maxP;
int max(int i,int j)
{
if(i > j) return i;
return j;
}
int main()
{
int testcase,i,j,k;
scanf("%d",&testcase);
while(testcase--)
{
int ans = 0;
scanf("%d%d%d",&T,&maxP,&W);
for(i=1;i<=T;i++)
{
scanf("%d%d%d%d",&data[i].APi,&data[i].BPi,&data[i].ASi,&data[i].BSi);
}
for(i=1;i<=T;i++)
for(j=0;j<=maxP;j++)
res[i][j] = -1000000;
for(i=1;i<=W+1;i++)
for(j=0;j<=data[i].ASi;j++)
res[i][j] = -j*data[i].APi;
for(i=2;i<=T;i++)
{
for(j=0;j<=maxP;j++)
res[i][j] = max(res[i][j],res[i-1][j]);
//由i-w-1天买入，维护在i-w-1天总资产递增序列
qhead = qtail = 0;
if(i-W-1<1)
continue;
for(j=0;j<=maxP;j++)
{
qe tmp;
tmp.pos = j,tmp.res = res[i-W-1][j] + j*data[i].APi;
queue[qhead++] = tmp;
while(qhead > qtail + 1 && queue[qhead-1].res > queue[qhead-2].res)
{
qhead--;
queue[qhead-1] = tmp;
}
while(qhead > qtail + 1 && data[i].ASi + queue[qtail].pos < j )
qtail++;
res[i][j] = max(res[i][j],res[i-W-1][queue[qtail].pos] - data[i].APi * (j - queue[qtail].pos));
}
qhead = qtail = 0;
for(j=maxP;j>=0;j--)
{
qe tmp;
tmp.pos = j,tmp.res = res[i-W-1][j] + j*data[i].BPi;
queue[qhead++] = tmp;
while(qhead > qtail + 1 && tmp.res > queue[qhead-2].res)
{
qhead--;
}
queue[qhead-1] = tmp;
while(qhead > qtail + 1 && queue[qtail].pos - data[i].BSi > j)
qtail++;
res[i][j] = max(res[i][j],res[i-W-1][queue[qtail].pos] + data[i].BPi * (queue[qtail].pos - j));
}
}
for(i=0;i<=maxP;i++)
if(ans < res[T][i])
ans = res[T][i];
printf("%d\n",ans);
}
return 0;
}