XJOI 夏令营501-511测试11 游戏
Alice和Bob两个人正在玩一个游戏,游戏有很多种任务,难度为p的任务(p是正整数),有1/(2^p)的概率完成并得到2^(p-1)分,如果完成不了,得0分。一开始每人都是0分,从Alice开始轮流做任务,她可以选择任意一个任务来做;而Bob只会做难度为1的任务。只要其中有一个人达到n分,即算作那个人胜利。求Alice采取最优策略的情况下获胜的概率。
输入格式:
一个正整数n,含义如题目所述。
输出格式:
一个数,表示Alice获胜的概率,保留6位小数。
样例输入:
1
样例输出:
0.666667
数据范围:
对于30%的数据,n≤10
对于100%的数据,n≤500
时间限制:
1sec
空间限制:
128MB
概率DP
可以发现,对于每个游戏的状态,都是可以有前几个装态转移过来的
所以记dp[i][j]表示Ailce取得了i分,Bob取得了j分的最优概率
那么dp[n][j]($0\leq j< n$)=1,其他状态都为0
因为进行游戏时有可能失败,那么dp[i][j]可能转移到自己
那么对于转移方程,可以将dp[i][j]移项移到一边,进行转移
设当前选择p个游戏
$dp[i][j]=dp[i][j]*(1-\frac{1}{2^{p}})*\frac{1}{2}+dp[i+2^{p-1}][j]*\frac{1}{2^{p}}*\frac{1}{2}+dp[i][j+1]*(1-\frac{1}{2^{p}})*\frac{1}{2}+dp[i+2^{p-1}][j+1]*\frac{1}{2^{p}}*\frac{1}{2}$
$(\frac{1}{2}+\frac{1}{2^{p+1}})dp[i][j]=dp[i+2^{p-1}][j]*\frac{1}{2^{p}}*\frac{1}{2}+dp[i][j+1]*(1-\frac{1}{2^{p}})*\frac{1}{2}+dp[i+2^{p-1}][j+1]*\frac{1}{2^{p}}*\frac{1}{2}$
$dp[i][j]=\frac{dp[i+2^{p-1}][j]*\frac{1}{2^{p}}*\frac{1}{2}+dp[i][j+1]*(1-\frac{1}{2^{p}})*\frac{1}{2}+dp[i+2^{p-1}][j+1]*\frac{1}{2^{p}}*\frac{1}{2}}{\frac{1}{2}+\frac{1}{2^{p+1}}}$
然后对于每一个p,dp[i][j]取最大值即可
注意,此处是由较大的i,j推到较小的i,j,需要注意边界条件
#include <bits/stdc++.h>
using namespace std;
int n,z[20];
double dp[2010][2010];
int main()
{
scanf("%d",&n);
for (int i=0;i<=n;i++)
dp[n][i]=1;
z[0]=1;
for (int i=1;i<=15;i++)
z[i]=z[i-1]*2;
for (int i=n-1;i>=0;i--)
{
for (int j=n-1;j>=0;j--)
{
for (int p=1;p<=10;p++)
{
double now,r,sum=0;;
now=1/((double)z[p]);
r=1-0.5*(1-now);//r为转移方程的分母
sum=dp[min(i+z[p-1],n)][j]*now*0.5+dp[i][j+1]*(1-now)*0.5+dp[min(i+z[p-1],n)][j+1]*now*0.5;
dp[i][j]=max(dp[i][j],sum/r);
} }
}
printf("%.6lf\n",dp[0][0]);
}
最新文章
- 深入理解javascript函数系列第四篇——ES6函数扩展
- Android开发3:Intent、Bundle的使用和ListView的应用 、RelativeLayout(相对布局)简述(简单通讯录的实现)
- AppBox升级进行时 - 拥抱Entity Framework的Code First开发模式
- Microsoft Visual Studio has encountered a problem
- Python函数参数默认值的陷阱和原理深究";
- 利用jquery实现网站中对应栏目下面内容切换效果。
- jsoup解析HTML
- CGRect 结构体的另外一种写法
- MongoDB之四( 索引操作)
- ios 6 横竖屏转换
- linux 下停止java jar包 shell
- C++笔记十七:C语言中 “冒牌货”const和const符号表
- Intellij IDEA 环境 tomcat 启动设置
- Vue 根组件,局部,全局组件 | 组件间通信,案例组件化
- iframe边距问题解决
- Centos6.8操作防火墙
- hbase 部署
- objects &; values &; types
- CentOS7安装weblogic集群思路梳理
- RESTORE DATABASE命令还原SQLServer 2005 数据库
热门文章
- 《凤凰项目:一个IT运维的传奇故事》读书笔记
- JavaScript查找字符串中给定字符出现的位置以及次数
- nginx完美支持thinkphp3.2.2(需配置URL_MODEL=>;1 pathinfo模式)
- linux的安装3.7python
- CV学习日志:CV开发常用库及其头文件
- Springboot+JPA下实现简易爬虫:豆瓣电视剧数据
- Linux Centos7 安装Docker-CE
- springMvc配置拦截器无效
- java 图片相似度算法
- 【CF1428D】Bouncing Boomerangs 题解