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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2037][Sdoi2008]Sue的小球  

2015-01-04 14:57:48|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2037: [Sdoi2008]Sue的小球

题面存在的问题:vi不会小于0

上道题交错位置的题,于是(颓了一上午之后)顺势就来做了,结果……
啊啊啊啊啊啊啊啊啊啊你妹啊做过的题还想了一节课是什么情况
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int N = 1000+10;
int n,m,X0,nl,nr,sl[N],sr[N],sum[N];
struct Data{int x,y,v;}data[N];
const double eps = 1e-9;
double f[N][N][2],all,DK = 1.0/1000;
int scan(){int i=0;scanf("%d",&i);return i;}
bool operator < (Data a,Data b){return a.x < b.x;}
inline int dis(int i,int j){return sum[j] - sum[i];}
inline double cost(int i,int j){return (sl[i+1]+sr[j+1])*DK;}
int main(){
//freopen("in.txt","r",stdin);
//printf("%f",sizeof(f)/1024.0/1024);
int i,j,a,b,c,st;
n = scan();X0 = scan();
for(i=1;i<=n;i++)data[i].x = scan();
for(i=1;i<=n;i++)b = data[i].y = scan(),all += b*DK;
for(i=1;i<=n;i++)data[i].v = scan();

data[++n] = (Data){X0,0,0};
sort(data+1,data+1+n);
data[0].x = data[1].x;
for(i=1;i<=n;i++){
if(data[i].x == X0 && data[i].y == 0)st = i;
sum[i] = sum[i-1] + data[i].x - data[i-1].x;
}
nl = st-1;nr = n-st;
for(i=nl;i;i--)sl[i] = sl[i+1] + data[st-i].v;
for(i=nr;i;i--)sr[i] = sr[i+1] + data[st+i].v;
f[0][0][1] = f[0][0][0] = 0;
for(i=0;i<=nl;i++)
for(j=0;j<=nr;j++)
if(i!=0 || j!=0){
f[i][j][0] = 1e50;
f[i][j][1] = 1e50;
//if(i==0 && j==1) printf("cf");
//0
double tmp[2];
if(i-1 >= 0){
tmp[0] = f[i-1][j][0]+dis(st-i,st-i+1)*cost(i-1,j);
tmp[1] = f[i-1][j][1]+dis(st-i,st+j)*cost(i-1,j);
//if(tmp[0]<0 || tmp[1]<0) printf("%d %d\n",i,j);
f[i][j][0] = min(tmp[0],tmp[1]);
}
//1
if(j-1 >= 0){
tmp[0] = f[i][j-1][0]+dis(st-i,st+j)*cost(i,j-1);
tmp[1] = f[i][j-1][1]+dis(st+j-1,st+j)*cost(i,j-1);
//if(tmp[0]<0 || tmp[1]<0) printf("%d %d\n",i,j);
f[i][j][1] = min(tmp[0],tmp[1]);
}
//else
if(f[i][j][0] > f[i][j][1])f[i][j][0] = min(f[i][j][0] , f[i][j][1] + dis(st-i,st+j)*cost(i,j));
else f[i][j][1] = min(f[i][j][1] , f[i][j][0] + dis(st-i,st+j)*cost(i,j));
}
//printf("%.3f %.3f\n",f[0][2][0],f[0][2][1]);
double ans=min(f[nl][nr][0],f[nl][nr][1]);
//printf("%.3f %.3f\n",f[nl][nr][0],f[nl][nr][1]);
printf("%.3f",all - ans + eps);
return 0;
}

题解:
DP
我们把包括X0在内的所有位置排序之后发现一个性质,如果我们拿了X0左边的第i个球,那么左边第i-1个球也一定被拿了,右边同理。
所以可以f[i][j]表示左边拿到第i个右边最远拿到第j个
但是这样还是有问题,我们要想知道下一步得到球的价值的话还需要知道当前的时间,那把时间做成状态?明显不行
我们发现每一秒所有小球减少的价值是一个定值,那么f[i][j]表示当前已经减少的价值就可以消除时间的影响了。
所有f[i][j][k]表示左边拿到了第i个,右边拿到了第j个,k=0则最后停在左边,否则停在右边。
让f最小化就行了
注意转移的时候f[i][j][0]和f[i][j][1]之间还要互相转移一下
  评论这张
 
阅读(104)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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