[SCOI 第一试 股票交易]动态规划、单调队列优化

【题目】

Description

最近lxhgww又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。
通过一段时间的观察，lxhgww预测到了未来T天内某只股票的走势，第i天的股票买入价为每股APi，第i天的股票卖出价为每股BPi（数据保 证对于每个i，都有APi>=BPi），但是每天不能无限制地交易，于是股票交易所规定第i天的一次买入至多只能购买ASi股，一次卖出至多只能卖 出BSi股。
另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔W 天，也就是说如果在第i天发生了交易，那么从第i+1天到第i+W天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的 股票数不能超过MaxP。
在第1天之前，lxhgww手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然，T天以后，lxhgww想要赚到最多的钱，聪明的 程序员们，你们能帮助他吗？

Input

输入数据第一行包括3个整数，分别是T，MaxP，W。
接下来T行，第i行代表第i-1天的股票走势，每行4个整数，分别表示APi，BPi，ASi，BSi。

Output

输出数据为一行，包括1个数字，表示lxhgww能赚到的最多的钱数。

Sample Input

5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1

Sample Output

3

Hint

【数据范围】
对于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 【算法分析】
该题很容易得出方程和状态：
F[i,j]表示第i天，手上有j点股份，所得的最大收入。
然后预处理从第i天开始买的情况。
即F[i,j]=-buyprize[i]*j   其中 j<=buylimit[i]。
然后是转移。
转移分两种，一种是卖，一种是买。
F[i,j]=max{
1、F[i-1,j] 就是第i天不买股份，手上依然j点股份。
2、F[i-w-1,k] – buyprize[i]*(j-k) 其中 1<=j-k<=buylimit[i]   表示今天买j-k那么多股份。
3、F[i-w-1,k] + sellprize[i]*(k-j) 其中 1<=k-j<=selllimit[i]   表示今天卖k-j这么多股份。
}
然后第一种方案直接转移。然后后面两种，显然可以用单调队列优化。
最终时间复杂度O(T*maxp)
【CODE】
#include #include #include const int N=2005;
int T,maxp,W;
int inp[N],outp[N],inlimit[N],outlimit[N];
int F[N][N];
struct queue{int p,f;}q[N];

void input(){
scanf("%d%d%d",&T,&maxp,&W);
for (int i=1;i<=T;i++)
scanf("%d%d%d%d",&inp[i],&outp[i],&inlimit[i],&outlimit[i]);
}

inline int min(int x,int y){return xinline int max(int x,int y){return x>y?x:y;}

void dp(){
int i,j,k,h,t;
int *pf,*f;
memset(F,200,sizeof(F));
for (i=1;i<=T;i++){
F[i][0]=0;
for (j=1;j<=min(inlimit[i],maxp);j++) F[i][j]=-inp[i]*j;
}
for (i=2;i<=T;i++){
pf=F[i-W-1];
f=F[i];
for (j=0;j<=maxp;j++) F[i][j]=max(F[i][j],F[i-1][j]);
if (i pf=F[i-W-1];
f=F[i];
h=t=0; q[0].p=0; q[0].f=pf[0];
for (j=1;j<=maxp;j++){
while (h<=t && j-q[h].p>inlimit[i]) h++;
if (h<=t) f[j]=max(f[j],q[h].f+(q[h].p-j)*inp[i]);
while (h<=t && q[t].f+(q[t].p-j)*inp[i] t++;
q[t].p=j;
q[t].f=pf[j];
}
h=t=0; q[0].p=maxp; q[0].f=pf[maxp];
for (j=maxp-1;j>=0;j–){
while (h<=t && q[h].p-j>outlimit[i]) h++;
if (h<=t) f[j]=max(f[j],q[h].f+(q[h].p-j)*outp[i]);
while (h<=t && q[t].f+(q[t].p-j)*outp[i] t++;
q[t].p=j;
q[t].f=pf[j];
}
}
}

void output(){
int ans=0;
for (int i=0;i<=maxp;i++)
ans=max(ans,F[T][i]);
printf("%dn",ans);
}

int main(){
freopen("trade.in","r",stdin);
freopen("trade.out","w",stdout);
input();
dp();
output();
}