股票交易
【题目描述】
最近lxhgww又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。
通过一段时间的观察，lxhgww预测到了未来T天内某只股票的走势，第i天的股票买入价为每股APi，第i天的股票卖出价为每股BPi（数据保证对于每个i，都有APi>=BPi），但是每天不能无限制地交易，于是股票交易所规定第i天的一次买入至多只能购买ASi股，一次卖出至多只能卖出BSi股。
另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔W天，也就是说如果在第i天发生了交易，那么从第i+1天到第i+W天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的股票数不能超过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)
为了优化复杂度，我们考虑在某一天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) 发现，h[j]的转移都是在前面固定的一天的j之前的不超过AS[t]的一段区间转移过来，于是考虑用单调队列。
但转移的值会随着j的改变而改变，无法用单调队列，所以考虑化简式子：
如果有p,q满足p,q∈[j-AS[t], j-1] 且 g[p] - AP[t] * (j - p) > g[q] - AP[t] * (j - q)， 则对于状态j来说，决策p要优于决策q
化简得：g[p] + p * AP[t] > g[q] + q * AP[t]，即决策的好坏由本身决定，与所要转移的状态无关。
转移(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;
}