2018.08.30 游戏(概率dp)
题目描述
Alice 和 Bob 两个人正在玩一个游戏,游戏有很多种任务,难度为 p 的任务(p是正整数),有 1/(2^p) 的概率完成并得到 2^(p-1) 分,如果完成不了,得 0 分。一开始每人都是 0 分,从 Alice 开始轮流做任务,她可以选择任意一个任务来做;而 Bob 只会做难度为 1 的任务。只要其中有一个人达到 n 分,即算作那个人胜利。求 Alice 采取最优策略的情况下获胜的概率。
输入格式
一个正整数 n ,含义如题目所述。
输出格式
一个数,表示 Alice 获胜的概率,保留 6 位小数。
样例数据 1
输入
1
输出
0.666667
备注
【数据范围】
对于 30% 的数据,n≤10
对于 100% 的数据,n≤500
概率dp入门题吧。
令f[i][j]表示Alice拿i分,Bob拿j分时的最优概率。
假设这一轮Alice选择难度为p的任务,且2^p=k。
显然有
f[i][j]=f[i+k][j]/4k+f[i+k][j+1]/4k+f[i][j+1]∗(2k−1)/4k+f[i][j]∗(2k−1)/4k" role="presentation" style="position: relative;">f[i][j]=f[i+k][j]/4k+f[i+k][j+1]/4k+f[i][j+1]∗(2k−1)/4k+f[i][j]∗(2k−1)/4kf[i][j]=f[i+k][j]/4k+f[i+k][j+1]/4k+f[i][j+1]∗(2k−1)/4k+f[i][j]∗(2k−1)/4k
合并同类项之后变成了:
f[i][j]=(f[i+k][j]+f[i+k][j+1]+f[i][j+1]∗(2k−1))/(2k+1)" role="presentation" style="position: relative;">f[i][j]=(f[i+k][j]+f[i+k][j+1]+f[i][j+1]∗(2k−1))/(2k+1)f[i][j]=(f[i+k][j]+f[i+k][j+1]+f[i][j+1]∗(2k−1))/(2k+1)
代码:
#include<bits/stdc++.h>
#define N 505
using namespace std;
int n;
double f[N][N];
int main(){
cin>>n;
for(int i=0;i<=n;++i)f[n][i]=1.0;
for(int i=n-1;i>=0;--i)
for(int j=n-1;j>=0;--j){
double tmp=0.0;
for(int k=1;k/2<=n;k<<=1){
int l=min(k+i,n);
tmp=max(tmp,(f[l][j]+f[l][j+1]+f[i][j+1]*(2*k-1))/(2*k+1));
}
f[i][j]=tmp;
}
printf("%lf",f[0][0]);
return 0;
}
最新文章
- 传入的表格格式数据流(TDS)远程过程调用(RPC)协议流不正确。此 RPC 请求中提供了过多的参数。最多应为 2100
- PHP form 表单传参明细研究
- haproxy simple cfg
- centos linux
- CRM创建物料FM2
- POJ2451 Uyuw&#39;s Concert(半平面交)
- Oracle数据库自我总结(转)
- SQL-LINQ-Lambda 语法对照
- MB_CHANGE_DOCUMENT使用方法
- vs.net 2013 Saffolding功能扩展
- C#中Console.WriteLine()函数输出格式详解
- C#3.0导航
- [20180822]session_cached_cursors与子游标堆0.txt
- .net core Identity集成IdentityServer(2) 实现IprofileService接口在accesstoken中增加自定义claims
- Latex: 设置 threeparttable footnote 行宽度
- spring boot打jar包(maven对jar和lib分离)
- try cache
- dubbo初学,快速体验
- configure: error: You need a C++ compiler for C++ support.[系统缺少c++环境]
- 【LOJ】#2523. 「HAOI2018」奇怪的背包
热门文章
- java Export Excel POI 转
- VBA 连接文本的自定义函数(可用于数组公式)
- HIBERNATE知识复习记录2-继承关系
- Can not find the tag library descriptor for ";http://www.springframework.org/tags";
- Haskell语言学习笔记(27)Endo, Dual, Foldable
- ubuntu ftp 建立匿名用户 [转]
- 【Java】JVM(五)、虚拟机类加载机制
- ReactNative手势解锁(react-native-ok-gesture-password)
- java &;&;与||短路的详解
- php去除bom