cf 540D D. Bad Luck Island 概率dp
来源：程序员人生 发布时间：2015-07-02 08:40:34 阅读次数：3380次
链接：http://codeforces.com/contest/540/problem/D
题意：1个岛上有石头人，剪刀人，布人，每天会有两个人相遇，根据相克会死掉1个人。问最后只剩下石头人的概率，只剩剪刀人的概率，布人的概率。
做法：dp[i][j][k] 代表有i个石头，j个剪刀，k个布的概率。
以剪刀和布相遇为例，会有转移 dp[i][j][k⑴]+=dp[i][j][k]*j*k/(i+j+k)/(i+j+k⑴) 。
但是这是不够的，由于还有平局的情况。平局的时候，状态又转移回了dp[i][j][k]，又从原状态开始转移，所以转移的比例还是1样的。
所以可以直接把 所有的转移概率相加，然后在转移的时候除掉。转移方程变成dp[i][j][k⑴]+=dp[i][j][k]*j*k/(i+j+k)/(i+j+k⑴)/tem;
tem为不是平局的概率总和。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <malloc.h>
#include <ctype.h>
#include <math.h>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#include <stack>
#include <queue>
#include <vector>
#include <deque>
#include <set>
#include <map>
#define INF 999999999
#define eps 0.00001
#define LL __int64d
#define pi acos(⑴.0)
double dp[110][110][110];
int main()
{
int shi,jian,bu;
while(scanf("%d%d%d",&shi,&jian,&bu)!=EOF)
{
memset(dp,0,sizeof dp);
dp[shi][jian][bu]=1;
for(int i=shi;i>=0;i--)
{
for(int j=jian;j>=0;j--)
{
for(int k=bu;k>=0;k--)
{
//printf("%d %d %d %lf
",i,j,k,dp[i][j][k]);
if(i+j==0||i+k==0||j+k==0)
continue;
double tem=0;
if(k!=0)
tem+=1.0*j*k/(i+j+k)/(i+j+k⑴);
if(j!=0)
tem+=1.0*j*i/(i+j+k)/(i+j+k⑴);
if(i!=0)
tem+=1.0*i*k/(i+j+k)/(i+j+k⑴);
if(k!=0)
dp[i][j][k⑴]+=dp[i][j][k]*j*k/(i+j+k)/(i+j+k⑴)/tem;
if(j!=0)
dp[i][j⑴][k]+=dp[i][j][k]*j*i/(i+j+k)/(i+j+k⑴)/tem;
if(i!=0)
dp[i⑴][j][k]+=dp[i][j][k]*i*k/(i+j+k)/(i+j+k⑴)/tem;
}
}
}
double aj=0;
double as=0,ab=0;
for(int i=1;i<=jian;i++)
{
aj+=dp[0][i][0];
}
for(int i=1;i<=shi;i++)
{
as+=dp[i][0][0];
}
for(int i=1;i<=bu;i++)
{
ab+=dp[0][0][i];
}
printf("%.9lf %.9lf %.9lf
",as,aj,ab);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
