[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();
}

加入对话

2条评论

留下评论

回复 edward_mj 取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注