注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ1855][Scoi2010]股票交易  

2015-03-20 15:12:45|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1855: [Scoi2010]股票交易

题目保证不会爆longlong

对于100%的数据,0<=W<T<=2000,1<=MaxP<=2000

对于所有的数据,1<=BPi<=APi<=1000,1<=ASi,BSi<=MaxP


先是想错了然后暴力调不对……

#include<cstdio>
#include<cstdlib>
#include<deque>
#include<algorithm>
using namespace std;
const int N = 2200;
const int MAX = 2.1E9;
int n,m,w,buy[N][2],lim[N][2],f[N][N];
int scan(){int i=0;scanf("%d",&i);return i;}
int dui[N],dl,dr,pos[N];
int main(){
int i,j;
//freopen("in.txt","r",stdin);
n=scan();m=scan();w=scan();
for(i=1;i<=n;i++){
scanf("%d%d%d%d",&buy[i][0],&buy[i][1],&lim[i][0],&lim[i][1]);
}
for(i=1;i<=n;i++)
for(j=0;j<=m;j++){
if(j<=lim[i][0])f[i][j] = -j*buy[i][0];
else f[i][j]=-MAX;
}

for(i=2;i<=n;i++){
for(j=0;j<=m;j++)
f[i][j] = max(f[i][j],f[i-1][j]);
int i2=i-w-1;
if(i2<=0)continue;
//buy
dl=1;dr=0;
for(j=0;j<=m;j++){
//pop front
while(dl<=dr && j-pos[dl] > lim[i][0])dl++;
if(dl<=dr)f[i][j] = max(f[i][j],dui[dl]-j*buy[i][0]);
//push now
int val = f[i2][j]+j*buy[i][0];
while(dl<=dr && dui[dr]<=val)dr--;
dr++;
dui[dr] = val;
pos[dr] = j;
}

//sell
dl=1;dr=0;
for(j=m;j>=0;j--){
//pop front
while(dl<=dr && pos[dl]-j > lim[i][1])dl++;
if(dl<=dr)f[i][j] = max(f[i][j],dui[dl]-j*buy[i][1]);
//push now
int val = f[i2][j]+j*buy[i][1];
while(dl<=dr && dui[dr]<=val)dr--;
dr++;
dui[dr] = val;
pos[dr] = j;
}
}
printf("%d\n",f[n][0]);
return 0;
}

题解:
错误的做法:
一次买/卖尽可能多地操作
因为有限制,可能你需要分两次卖出,第一次出售价格偏低,少卖一些,第二次比较高,多卖一些
  评论这张
 
阅读(3)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017