URAL 1936 Roshambo(求期望)
Description
Input
Output
题目大意:n个人玩石头剪刀布(一起上的),每一round若平局则继续,否则输的出局,赢的留下来,进入下一round。直到剩下一个人,问期望进行多少round。
思路:递推。令dp[n]代表n个人的期望结束盘数(也就是我们要的答案)。
令ret代表n个人,这一场不平手的结束盘数。枚举赢的人数 i ,那么赢的人数为 i 的概率 p 为从 n 个人里面选 i 个人赢,其中这 i 个人的选择有3种,这 i 个人都出前面选的那一种,概率为 (1/3)^i ,剩下的n-i个人,都选被前面选的那种打败的一种,概率为 (1/3)^(n-i)。然后赢了之后,就是剩下 i 个人,也就是 i 个人结束游戏的期望盘数dp[i] + 1,符合递推条件。
令q为平局的概率,这个很容易求,q = 1 - sum{p},p就是前面的所有非平局的概率。
ret = sum{(dp[i]+1) * c[n][i] * 3 * (1/3)^i * (1/3)^(n-i)} = sum{(dp[i]+1) * c[n][i] * (1/3)^(i-1)}
那么dp[n] = (1-q)*ret + q*(1-q)*(1+ret) + q^2*(1-q)*(2+ret) + q^3*(1-q)*(3+ret) + ……
//提取出1-q
=(1-q)(ret + (1+ret)*q + (2+ret)*q^2 + (3+ret)*q^3 + ……)
//把ret提出来,分别求极限
=(1-q)(ret/(1-q) + q/(1-q)^2)
=ret + q/(1-q)
然后一切就好办了。
PS:代码被我各种合并已经跟前面讲的大不一样了……
PS2:前面写得好乱不知道有没有写错的啊……
PS3:代码中的q是上面的1-q,也就是sum{p},因为不改成这样会出现精度误差导致无法AC。具体原因我想了一下,比如q原来是1,当q减去一个很小的数的时候,破了double的精度,那么q还是1,然后这个数就被丢掉了,造成了误差。
代码(31MS)(递推会快一点的……):
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <iomanip>
using namespace std;
typedef long long LL; const int MAXN = ;
const double EPS = 1e-; double dp[MAXN];
double c[MAXN][MAXN]; double C(int n, int m) {
if(c[n][m] > EPS) return c[n][m];
if(n == m) return c[n][m] = ;
if(m == ) return c[n][m] = n;
return c[n][m] = C(n - , m - ) + C(n - , m);
} double solve(int n) {
if(n == ) return ;
if(dp[n] > EPS) return dp[n];
double ret = , q = ;
for(int i = ; i < n; ++i) {
double p = C(n, i) * pow(./, n - );
ret += p * (solve(i));
q += p;
}
return dp[n] = (ret + ) / (q);
} int main() {
int n;
while(scanf("%d", &n) != EOF) {
cout.precision();
cout<<setiosflags(ios::fixed)<<solve(n)<<endl;
}
}
最新文章
- 建站技能get(1)— Asp.net MVC快速集成ckplayer网页视频播放器
- 七牛php sdk 生成上传凭证时出现 undefined function Qiniu_SetKeys()
- Python图表绘制:matplotlib绘图库入门
- JS-定时器管理实例函数封装
- Design Pattern :Factory and Reflect in java
- Linux 下让进程在后台可靠运行的几种方法
- Global build settings
- git merge 分支
- javascript语句语义大全(6)
- 浅入深出Vue系列
- hive 一次更新多个分区的数据
- Cisco IP 电话 将它的voice mail 发送到手机
- Ubuntu调节屏幕亮度
- 牛刀小试MySQL--基于GTID的replication
- Android学习系列(17)--App列表之圆角ListView(续)
- ASP.NET Web API接受AngualrJS的QueryString的两种方式
- Null value was assigned to a property of primitive type setter of";原因及解决方法
- Visual Studio 2013百度云下载地址
- UCI一位搞theory的教授列的一些数学方面的比较趣味性的网页
- Window对象的判定方法