股票交易
【題目描述】
最近lxhgww又迷上了投資股票，通過一段時間的觀察和學習，他總結出了股票行情的一些規(guī)律。
通過一段時間的觀察，lxhgww預測到了未來T天內某只股票的走勢，第i天的股票買入價為每股APi，第i天的股票賣出價為每股BPi（數據保證對于每個i，都有APi>=BPi），但是每天不能無限制地交易，于是股票交易所規(guī)定第i天的一次買入至多只能購買ASi股，一次賣出至多只能賣出BSi股。
另外，股票交易所還制定了兩個規(guī)定。為了避免大家瘋狂交易，股票交易所規(guī)定在兩次交易（某一天的買入或者賣出均算是一次交易）之間，至少要間隔W天，也就是說如果在第i天發(fā)生了交易，那么從第i+1天到第i+W天，均不能發(fā)生交易。同時，為了避免壟斷，股票交易所還規(guī)定在任何時間，一個人的手里的股票數不能超過MaxP。
在第1天之前，lxhgww手里有一大筆錢（可以認為錢的數目無限），但是沒有任何股票，當然，T天以后，lxhgww想要賺到最多的錢，聰明的程序員們，你們能幫助他嗎？
【輸入】
輸入數據第一行包括3個整數，分別是T，MaxP，W。
接下來T行，第i行代表第i-1天的股票走勢，每行4個整數，分別表示APi，BPi，ASi，BSi。
【輸出】
輸出數據為一行，包括1個數字，表示lxhgww能賺到的最多的錢數。
【樣例輸入】
5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1
【樣例輸出】
3
【數據范圍】
對于30%的數據，0<=W<T<=50,1<=MaxP<=50
對于50%的數據，0<=W<T<=2000,1<=MaxP<=50
對于100%的數據，0<=W<T<=2000,1<=MaxP<=2000
對于所有的數據，1<=BPi<=APi<=1000,1<=ASi,BSi<=MaxP
=================================================================================
首先寫個裸的DP：
f[i][j] 表示前i天并且第i天可以操作，手里有j股股票的時候最多能賺多少錢，轉移為：
f[i][j] = max{f[i-1][j], //不干事
f[i-W-1][j-k] - AP[i-W-1] * k, // 買 , i-W-1>=0 && j-k>=0 && k<=AS[i-W-1]
f[i-W-1][j+k] + BP[i-W-1] * k} // 賣, i-W-1>=0 && j+k<=MaxP && k<=BS[i-W-1]
復雜度O(T * MaxP^2)
為了優(yōu)化復雜度，我們考慮在某一天i時，上一次可以操作的時間為t = i-W-1
令g[j] = f[t][j], h[j] = f[i][j]
不考慮不干事的轉移則有：
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)
考慮轉移(1) 發(fā)現，h[j]的轉移都是在前面固定的一天的j之前的不超過AS[t]的一段區(qū)間轉移過來，于是考慮用單調隊列。
但轉移的值會隨著j的改變而改變，無法用單調隊列，所以考慮化簡式子：
如果有p,q滿足p,q∈[j-AS[t], j-1] 且 g[p] - AP[t] * (j - p) > g[q] - AP[t] * (j - q)， 則對于狀態(tài)j來說，決策p要優(yōu)于決策q
化簡得：g[p] + p * AP[t] > g[q] + q * AP[t]，即決策的好壞由本身決定，與所要轉移的狀態(tài)無關。
轉移(2)類似。
所以可以用單調隊列維護g[p] + p * AP[t]，使轉移均攤O(1)，總復雜度降到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;
}