首页 > 代码库 > BZOJ 1855 股票交易（单调队列优化DP）
BZOJ 1855 股票交易（单调队列优化DP）
题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1855
题意：最近lxhgww又迷上了投资股票， 通过一段时间的观察和学习，他总结出了股票行情的一些规律。 通过一段时间的观察，lxhgww预测到了未来T天内某只股票的走势，第i天的股票买入价为每股APi，第i天的股票卖出价为每股BPi（数据保证对于每 个i，都有APi>=BPi），但是每天不能无限制地交易，于是股票交易所规定第i天的一次买入至多只能购买ASi股，一次卖出至多只能卖出BSi 股。 另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔W天，也就 是说如果在第i天发生了交易，那么从第i+1天到第i+W天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的股票数不 能超过MaxP。 在第1天之前，lxhgww手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然，T天以后，lxhgww想要赚到最多的钱。
思路：设f[i][j]表示到第i天手里持有j的股票的最大收益，那么第i天有三种操作：
对于买入，我们对其变形：
那么可以用单调队列维护f[i-w-1][k]+ap[i]*k（因为对于固定的i，ap[i]是固定的），这样f[i][j]就能做到O(1)计算，而不必枚举k。卖出也一样。
struct node{ int x,y; node(){} node(int _x,int _y) { x=_x; y=_y; }};int f[N][N],n,m,w;node Q[N];int st,ed;int main(){ RD(n,m,w); int ap,bp,as,bs,i,j,k; FOR0(i,n+1) FOR0(j,m+1) f[i][j]=-INF; int ans=0; FOR1(i,n) { RD(ap,bp); RD(as,bs); for(j=0;j<=as;j++) f[i][j]=-ap*j; for(j=0;j<=m;j++) upMax(f[i][j],f[i-1][j]); k=i-w-1; if(k>=0) { st=ed=0; for(j=0;j<=m;j++) { while(st<ed&&Q[st].x<j-as) st++; while(st<ed&&Q[ed-1].y<=f[k][j]+ap*j) ed--; Q[ed++]=node(j,f[k][j]+ap*j); if(st<ed) upMax(f[i][j],Q[st].y-ap*j); } st=ed=0; for(j=m;j>=0;j--) { while(st<ed&&Q[st].x>j+bs) st++; while(st<ed&&Q[ed-1].y<=f[k][j]+bp*j) ed--; Q[ed++]=node(j,f[k][j]+bp*j); if(st<ed) upMax(f[i][j],Q[st].y-bp*j); } } upMax(ans,f[i][0]); } PR(ans);}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。