首页 > 代码库 > 51nod1450 闯关游戏
51nod1450 闯关游戏
题目来源: TopCoder
基准时间限制:1 秒 空间限制:131072 KB 分值: 320
一个游戏App由N个小游戏(关卡)构成,将其标记为0,1,2,..N-1。这些小游戏没有相互制约的性质,玩家可以任意时刻玩任意一个小游戏,且每个小游戏可以玩任意多次,一个小游戏玩一次消耗玩家恰好1min的时间。每个小游戏会根据玩家的表现返回3种结果:1)挑战失败;2)挑战成功并获得1颗星;3)挑战成功且获得2颗星。玩家可以多次挑战同一个小游戏,而且系统会记录玩家多次挑战中的最好成绩。(注意:两颗星优于一颗星优于挑战失败。)
这个游戏App通关需要同时满足2个条件:1)N个小游戏的系统记录的最好成绩都是成功;2)这N个小游戏的系统记录成绩中的星星总数至少是M颗。
根据一些统计,一个玩家在任一次玩第i个小游戏时,都会独立的发生以下结果:
* 有(1000 - X[i] - Y[i])*0.001的概率会挑战失败;
* 有 X[i]*0.001 的概率会挑战成功并获得一颗星;
* 有 Y[i]*0.001 的概率会挑战成功并获得两颗星.
其中1<=X[i],Y[i],且X[i]+Y[i]<=1000,且都为整数.
问一个玩家从安装完这个游戏App到这个游戏App通关,最优策略下需要花费时间的期望E。输出E的值,以min为该时间单位。(误差在1e-7内)
例如:样例中有两个小游戏,且两个小游戏每次玩必能通过,且有0.5的概率拿两颗星。玩家可以先各玩一个小游戏一次,有0.75的概率能拿至少3颗星;有0.25的概率只能拿2颗星,此时需要盯着一关不停的玩,直到得到两颗星,这需要1/2 * 1 + 1/4 * 2 + 1/8 * 3 + ... + 1/(2^k) * k + .... 次。所以,E = 0.75*2 + 0.25*(2 + 1/2 * 1 + 1/4 * 2 + 1/8 * 3 + ... + 1/(2^k) * k + .... )= 2.5。
这个游戏App通关需要同时满足2个条件:1)N个小游戏的系统记录的最好成绩都是成功;2)这N个小游戏的系统记录成绩中的星星总数至少是M颗。
根据一些统计,一个玩家在任一次玩第i个小游戏时,都会独立的发生以下结果:
* 有(1000 - X[i] - Y[i])*0.001的概率会挑战失败;
* 有 X[i]*0.001 的概率会挑战成功并获得一颗星;
* 有 Y[i]*0.001 的概率会挑战成功并获得两颗星.
其中1<=X[i],Y[i],且X[i]+Y[i]<=1000,且都为整数.
问一个玩家从安装完这个游戏App到这个游戏App通关,最优策略下需要花费时间的期望E。输出E的值,以min为该时间单位。(误差在1e-7内)
例如:样例中有两个小游戏,且两个小游戏每次玩必能通过,且有0.5的概率拿两颗星。玩家可以先各玩一个小游戏一次,有0.75的概率能拿至少3颗星;有0.25的概率只能拿2颗星,此时需要盯着一关不停的玩,直到得到两颗星,这需要1/2 * 1 + 1/4 * 2 + 1/8 * 3 + ... + 1/(2^k) * k + .... 次。所以,E = 0.75*2 + 0.25*(2 + 1/2 * 1 + 1/4 * 2 + 1/8 * 3 + ... + 1/(2^k) * k + .... )= 2.5。
Input
第一行两个个整数N,M,且1<=N<=2000,N <= M <= 2N接下来N行,每行两个整数,X[i]、Y[i],其中1<=X[i],Y[i],且X[i]+Y[i]<=1000
Output
一个浮点数,即期望E。确保E的精度与正解的绝对误差或相对误差小于1e-7。
Input示例
2 3500 500500 500
Output示例
2.5
数学问题 期望DP
充满迷惑地过了一题。
根据多年的游戏经验,我们应该先过掉所有的关,然后挑两星概率最大的还没过的关使劲儿怼。
由此我们将关卡按Y排序,先决策Y大的。
设f[i][j]表示还有i关要打,还剩j颗星要拿。
然后愉快地转移。
注释掉的代码是第一次写的版本,看上去很有道理但是只能过一半的点,输出结果和答案比较像,但是精度达不到1e-7
实际运行的版本借鉴了隔壁sdfzyhx的思路,先将m-=n以保证每关必过。
但是这不科学啊,我觉得我的写法也能保证每关必过啊? 就很迷茫
挣扎了一个小时,放弃了思考。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 using namespace std; 7 const int INF=0x3f3f3f3f; 8 const int mxn=4005; 9 int read(){10 int x=0,f=1;char ch=getchar();11 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}12 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}13 return x*f;14 }15 int n,m;16 double f[mxn][mxn];17 struct node{18 int x,y;19 bool operator < (const node &b)const{20 return y<b.y;21 }22 }a[mxn];23 int main(){24 int i,j;25 n=read();m=read();26 for(i=0;i<n;i++){27 a[i].x=read();a[i].y=read();28 }29 m-=n;//30 sort(a,a+n);31 for(i=0;i<=n;i++)32 for(j=0;j<=m;j++)33 f[i][j]=INF;34 f[n][m]=0;35 for(i=n-1;i>=0;i--){36 for(j=0;j<m;j++){37 f[i][j]=min(f[i][j],38 1000.0/(a[i].x+a[i].y)+f[i+1][j]*a[i].x/(a[i].x+a[i].y)+39 f[i+1][j+1]*a[i].y/(a[i].x+a[i].y)40 );41 f[i][j]=min(f[i][j],f[i+1][j+1]+1000.0/a[i].y);42 }43 f[i][m]=min(f[i][m],1000.0/(a[i].x+a[i].y)+f[i+1][m]);44 }45 /*46 for(i=n-1;i>=0;i--){47 for(j=m;j>=0;j--){48 f[i][j]=min(f[i][j],49 1000.0/(a[i].x+a[i].y)+f[i+1][j+1]*a[i].x/(a[i].x+a[i].y)+50 f[i+1][j+2]*a[i].y/(a[i].x+a[i].y));51 f[i][j]=min(f[i][j],f[i+1][j+2]+1000.0/a[i].y);52 }53 f[i][0]=min(f[i][0],1000.0/(a[i].x+a[i].y)+f[i+1][0]);54 }55 */56 printf("%.7f\n",f[0][0]);57 return 0;58 }
51nod1450 闯关游戏
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。