您當(dāng)前位置：首頁(yè) > php開(kāi)源 > 綜合技術(shù) > cf 540D D. Bad Luck Island 概率dp

cf 540D D. Bad Luck Island 概率dp

來(lái)源：程序員人生發(fā)布時(shí)間：2015-07-02 08:40:34 閱讀次數(shù)：3539次

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.

Input

The single line contains three integers r, s and p (1?≤?r,?s,?p?≤?100) ― the original number of individuals in the species of rock, scissors and paper, respectively.

Output

Print three space-separated real numbers: the probabilities, at which the rocks, the scissors and the paper will be the only surviving species, respectively. The answer will be considered correct if the relative or absolute error of each number doesn't exceed 10?-?9.

Sample test(s)

input
2 2 2

output
0.333333333333 0.333333333333 0.333333333333

input
2 1 2

output
0.150000000000 0.300000000000 0.550000000000

input
1 1 3

output
0.057142857143 0.657142857143 0.285714285714

鏈接：http://codeforces.com/contest/540/problem/D

題意：1個(gè)島上有石頭人，剪刀人，布人，每天會(huì)有兩個(gè)人相遇，根據(jù)相克會(huì)死掉1個(gè)人。問(wèn)最后只剩下石頭人的概率，只剩剪刀人的概率，布人的概率。

做法：dp[i][j][k] 代表有i個(gè)石頭，j個(gè)剪刀，k個(gè)布的概率。

以剪刀和布相遇為例，會(huì)有轉(zhuǎn)移 dp[i][j][k⑴]+=dp[i][j][k]*j*k/(i+j+k)/(i+j+k⑴) 。

但是這是不夠的，由于還有平局的情況。平局的時(shí)候，狀態(tài)又轉(zhuǎn)移回了dp[i][j][k]，又從原狀態(tài)開(kāi)始轉(zhuǎn)移，所以轉(zhuǎn)移的比例還是1樣的。

所以可以直接把所有的轉(zhuǎn)移概率相加，然后在轉(zhuǎn)移的時(shí)候除掉。轉(zhuǎn)移方程變成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; }

生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
程序員人生

------分隔線----------------------------

上一篇 Centos下配置端口轉(zhuǎn)發(fā)將80端口請(qǐng)求轉(zhuǎn)發(fā)至8080

下一篇 《操作系統(tǒng)》――解決并發(fā)進(jìn)程中與時(shí)間有關(guān)的錯(cuò)誤

分享到:

------分隔線----------------------------

為碼而活

積分：4237

15粉絲

7關(guān)注

欄目熱點(diǎn)

多多色-多人伦交性欧美在线观看-多人伦精品一区二区三区视频-多色视频-免费黄色视屏网站-免费黄色在线

cf 540D D. Bad Luck Island 概率dp