嚴(yán)重鄙視這一題，弄了N復(fù)雜的一個(gè)題意。。。做了好多天都沒(méi)想法，今天終于看著題解把它A掉了。。
其實(shí)單調(diào)隊(duì)列如果再?zèng)]有明顯的 max(i,i+K) 的情況下。。很難想得到。這個(gè)題目就是。
題意是說(shuō)一個(gè)人跟政府關(guān)系很好。知道了下面T天每天的股票價(jià)格。但是XX告訴他，兒子啊，我告訴你啊，你買(mǎi)股票要這么買(mǎi)，要不會(huì)被抓的。你手上的股票數(shù)最多不能超過(guò)maxP,而且某一天買(mǎi)賣(mài)之后，下次買(mǎi)賣(mài)的時(shí)間必須延后W天，你懂的。好了，下面告訴你T天的價(jià)格，你自己賺錢(qián)去吧。
這題的樸素的DP方程是這樣的: res[i][j] = res[i-W-1][k] + 買(mǎi)入或賣(mài)出的代價(jià) ( j-ASi<=k <=j+BSi )
有人會(huì)問(wèn)為什么只枚舉了i-W-1天呢？前面的日子呢？額。。。前面的日子已經(jīng)歸到i-W-1天啦。
好了，這破題。狀態(tài)復(fù)雜度: T*maxP,決策復(fù)雜度maxP。無(wú)懸念的超時(shí)了。
別人說(shuō)用單調(diào)隊(duì)列優(yōu)化就單調(diào)隊(duì)列優(yōu)化吧。
我們可以這樣想：假如i-w-1天那家伙持有的股票根據(jù)那天股票的價(jià)格換成了錢(qián)，就是都虛擬換成r[i-w-1][0]，這樣，我們可以知道，我們不會(huì)選擇錢(qián)少的決策的，因?yàn)槲覀儸F(xiàn)在得j是固定的，當(dāng)換算后的錢(qián)多的時(shí)候，無(wú)論怎樣決策都比錢(qián)少的好。。，好了，著就變成了第二句話(huà)那樣的模型了，直接換算出來(lái)，弄個(gè)丑陋的單調(diào)隊(duì)列出來(lái)，然后唧唧歪哇一大堆。
下面是代碼，寫(xiě)的比較長(zhǎng)，比較亂。糾結(jié)。。。。糾結(jié)。。。。
//單調(diào)隊(duì)列用法：求一段序列里的最值。 加上決策有序
//這個(gè)題 ： 決策的時(shí)候，把持有的股票數(shù)轉(zhuǎn)化出來(lái)，可知當(dāng)決策為 max(res[i-W-1][j-ASi],res[i-W-1][j+BSi]+k*BAi,BPi)時(shí)，
#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的股票賺的最多的錢(qián)
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天買(mǎi)入，維護(hù)在i-w-1天總資產(chǎn)遞增序列
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;
}