首页 > 代码库 > [Codeforces Round #301 (Div. 2) D]Bad Luck Island（概率Dp）
[Codeforces Round #301 (Div. 2) D]Bad Luck Island（概率Dp）
Description
The Bad Luck Island is inhabited by three kinds of species: r rocks, s scissors and p papers. At some moments of time two random individuals meet (all pairs of individuals can meet equiprobably), and if they belong to different species, then one individual kills the other one: a rock kills scissors, scissors kill paper, and paper kills a rock. Your task is to determine for each species what is the probability that this species will be the only one to inhabit this island after a long enough period of time.
Solution
题意：岛上有三种居民，石头r个，剪刀s个，布p个，他们会以相等的概率相遇，输的一方就被杀死，问最后剩下的是每种居民的概率各是多少
用f[i][j][k]表示表示还剩i个石头、j个剪刀、k个布这种状态出现的概率
f[i][j][k]=
f[i+1][j][k]*((i+1)*k)/((i+1)*j+(i+1)*k+j*k)
+f[i][j+1][k]*((j+1)*i)/(i*(j+1)+i*k+(j+1)*k)
+f[i][j][k+1]*((k+1)*j)/(i*j+i*(k+1)+j*(k+1))
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>using namespace std;int r,s,p;double f[107][107][107],ans[3];int main(){ scanf("%d%d%d",&r,&s,&p); f[r][s][p]=1; for(int i=r;i>=0;i--) { for(int j=s;j>=0;j--) { for(int k=p;k>=0;k--) { if(j&&k)f[i][j][k]+=f[i+1][j][k]*((i+1)*k)/((i+1)*j+(i+1)*k+j*k); if(i&&k)f[i][j][k]+=f[i][j+1][k]*((j+1)*i)/(i*(j+1)+i*k+(j+1)*k); if(i&&j)f[i][j][k]+=f[i][j][k+1]*((k+1)*j)/(i*j+i*(k+1)+j*(k+1)); } } } for(int i=1;i<=r;i++) for(int j=1;j<=s;j++) ans[0]+=f[i][j][0]; for(int i=1;i<=s;i++) for(int j=1;j<=p;j++) ans[1]+=f[0][i][j]; for(int i=1;i<=r;i++) for(int j=1;j<=p;j++) ans[2]+=f[i][0][j]; printf("%.12lf %.12lf %.12lf\n",ans[0],ans[1],ans[2]); return 0;}
[Codeforces Round #301 (Div. 2) D]Bad Luck Island（概率Dp）