股票交易
【題目描述】
最近lxhgww又迷上了投資股票，通過(guò)一段時(shí)間的觀察和學(xué)習(xí)，他總結(jié)出了股票行情的一些規(guī)律。
通過(guò)一段時(shí)間的觀察，lxhgww預(yù)測(cè)到了未來(lái)T天內(nèi)某只股票的走勢(shì)，第i天的股票買(mǎi)入價(jià)為每股APi，第i天的股票賣(mài)出價(jià)為每股BPi（數(shù)據(jù)保證對(duì)于每個(gè)i，都有APi>=BPi），但是每天不能無(wú)限制地交易，于是股票交易所規(guī)定第i天的一次買(mǎi)入至多只能購(gòu)買(mǎi)ASi股，一次賣(mài)出至多只能賣(mài)出BSi股。
另外，股票交易所還制定了兩個(gè)規(guī)定。為了避免大家瘋狂交易，股票交易所規(guī)定在兩次交易（某一天的買(mǎi)入或者賣(mài)出均算是一次交易）之間，至少要間隔W天，也就是說(shuō)如果在第i天發(fā)生了交易，那么從第i+1天到第i+W天，均不能發(fā)生交易。同時(shí)，為了避免壟斷，股票交易所還規(guī)定在任何時(shí)間，一個(gè)人的手里的股票數(shù)不能超過(guò)MaxP。
在第1天之前，lxhgww手里有一大筆錢(qián)（可以認(rèn)為錢(qián)的數(shù)目無(wú)限），但是沒(méi)有任何股票，當(dāng)然，T天以后，lxhgww想要賺到最多的錢(qián)，聰明的程序員們，你們能幫助他嗎？
【輸入】
輸入數(shù)據(jù)第一行包括3個(gè)整數(shù)，分別是T，MaxP，W。
接下來(lái)T行，第i行代表第i-1天的股票走勢(shì)，每行4個(gè)整數(shù)，分別表示APi，BPi，ASi，BSi。
【輸出】
輸出數(shù)據(jù)為一行，包括1個(gè)數(shù)字，表示lxhgww能賺到的最多的錢(qián)數(shù)。
【樣例輸入】
5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1
【樣例輸出】
3
【數(shù)據(jù)范圍】
對(duì)于30%的數(shù)據(jù)，0<=W<T<=50,1<=MaxP<=50
對(duì)于50%的數(shù)據(jù)，0<=W<T<=2000,1<=MaxP<=50
對(duì)于100%的數(shù)據(jù)，0<=W<T<=2000,1<=MaxP<=2000
對(duì)于所有的數(shù)據(jù)，1<=BPi<=APi<=1000,1<=ASi,BSi<=MaxP
=================================================================================
首先寫(xiě)個(gè)裸的DP：
f[i][j] 表示前i天并且第i天可以操作，手里有j股股票的時(shí)候最多能賺多少錢(qián)，轉(zhuǎn)移為：
f[i][j] = max{f[i-1][j], //不干事
f[i-W-1][j-k] - AP[i-W-1] * k, // 買(mǎi) , i-W-1>=0 && j-k>=0 && k<=AS[i-W-1]
f[i-W-1][j+k] + BP[i-W-1] * k} // 賣(mài), i-W-1>=0 && j+k<=MaxP && k<=BS[i-W-1]
復(fù)雜度O(T * MaxP^2)
為了優(yōu)化復(fù)雜度，我們考慮在某一天i時(shí)，上一次可以操作的時(shí)間為t = i-W-1
令g[j] = f[t][j], h[j] = f[i][j]
不考慮不干事的轉(zhuǎn)移則有：
h[j] = max{g[j-k] - AP[t] * k,
g[j+k] + BP[t] * k}
令p = j-k則：
h[j] = max{g[p] - AP[t] * (j-p), ................(1)
g[p] + BP[t] * (p-j)} ................(2)
考慮轉(zhuǎn)移(1) 發(fā)現(xiàn)，h[j]的轉(zhuǎn)移都是在前面固定的一天的j之前的不超過(guò)AS[t]的一段區(qū)間轉(zhuǎn)移過(guò)來(lái)，于是考慮用單調(diào)隊(duì)列。
但轉(zhuǎn)移的值會(huì)隨著j的改變而改變，無(wú)法用單調(diào)隊(duì)列，所以考慮化簡(jiǎn)式子：
如果有p,q滿足p,q∈[j-AS[t], j-1] 且 g[p] - AP[t] * (j - p) > g[q] - AP[t] * (j - q)， 則對(duì)于狀態(tài)j來(lái)說(shuō)，決策p要優(yōu)于決策q
化簡(jiǎn)得：g[p] + p * AP[t] > g[q] + q * AP[t]，即決策的好壞由本身決定，與所要轉(zhuǎn)移的狀態(tài)無(wú)關(guān)。
轉(zhuǎn)移(2)類似。
所以可以用單調(diào)隊(duì)列維護(hù)g[p] + p * AP[t]，使轉(zhuǎn)移均攤O(1)，總復(fù)雜度降到O(T * MaxP)
#include <iostream>
#define MAXN 4010
#define MAXP 2010
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define INFINITE (1<<30)
#define MAX(a,b) ((a) > (b) ? (a) : (b))
using namespace std;
int T,MaxP,W;
int AP[MAXN+1], BP[MAXN+1], AS[MAXN+1], BS[MAXN+1];
int n;
void Init()
{
scanf("%d%d%d",&n,&MaxP,&W);
for (int i = 1; i<=n; i++)
scanf("%d%d%d%d",&AP[i],&BP[i],&AS[i],&BS[i]);
}
int f[MAXN+1][MAXP+1];
int Ans = 0;
void Renew(int i, int j, int v){
if (i > n)
Ans = MAX(Ans, v);
else
f[i][j] = MAX(f[i][j], v);
}
class Queue{
public:
int head,tail,len;
int v[MAXP+1];
int p[MAXP+1];
void clear(){
head = 1, tail = 0;
}
void set(int len){
this->len = len;
}
void push(int pos, int val){
if (head<=tail && abs(pos - p[head])-1 > len) head++;
while (head<=tail && v[tail] <= val) tail--;
p[++tail] = pos, v[tail] = val;
}
int front(int j){
while (head<tail && abs(j-p[head]) > len) head++;
return p[head];
}
}q;
void Solve(){
for (int i = 0; i<=n+W+1; i++)
for (int j = 1; j<=MaxP; j++)
f[i][j] = -INFINITE;
for (int i = 1; i<=n; i++){
for (int j = 1; j<=AS[i]; j++)
f[i+W+1][j] = - AP[i] * j;
for (int j = AS[i]+1; j<=MaxP; j++)
f[i+W+1][j] = -INFINITE;
}
int asdf = 0;
for (int i = 1; i<=n+W+1; i++){
for (int j = 0; j<=MaxP; j++)
f[i][j] = MAX(f[i][j], f[i-1][j]);
int t;
/**//*
g[j] - AP * (i - j) > g[k] - AP * (i - k)
g[j] + AP * j > g[k] + AP * k
g[j] + BP * (j - i) > g[k] + BP * (j - i)
g[j] + BP * j > g[k] + BP * j
*/
if ((t = i-W-1) >= 1){
// Buy
q.clear(); q.set(AS[t]);
q.push(0, f[t][0]);
for (int j = 1; j<=MaxP; j++){
int tmp = q.front(j);
f[i][j] = MAX(f[i][j], f[t][tmp] - AP[t] * (j - tmp));
q.push(j, f[t][j] + AP[t] * j);
}
// Sell
q.clear(); q.set(BS[t]);
q.push(MaxP,f[t][MaxP] + BP[t] * MaxP);
for (int j = MaxP-1; j>=0; j--){
int tmp = q.front(j);
f[i][j] = MAX(f[i][j], f[t][tmp] + BP[t] * (tmp - j));
q.push(j, f[t][j] + BP[t] * j);
}
for (int j = 0; j<=MaxP; j++)
Ans = MAX(Ans, f[i][j]);
}
}
printf("%d\n",Ans);
}
int main(){
freopen("trade.in","r",stdin);
freopen("trade.out","w",stdout);
Init();
Solve();
return 0;
}