【Codeforces Round #301 (Div. 2) D】 Bad Luck Island

剪刀、石头、布各有r,s,p个生活在同一个村子里。
它们两两之间相遇的几率都相同(相遇后就会按照划拳的规则判断输赢,输的人就死掉了)。
问你最后只剩下剪刀，只剩下石头、只剩下布活着的概率。

【题解】

动态规划
如果从输赢方面去考虑的话很难找到解。
设f[i][j][k]表示石头，剪刀，布分别剩下i,j,k只活着的概率。
显然有i*j+i*k+j*k种可能。
而(i,j,k)这个状态,变成(i-1,j,k)这个状态,显然就是石头的个数减少1了。
那么就是石头遇到了布,也即其中的i*k种可能。
那么从(i,j,k)转移到(i-1,j,k)这个过程,就是f[i][j][k]*转移的概率。其中转移的概率=$\frac{i*k}{i*j+i*k+j*k}$
其他的转移同理
最后ans1 = f[i][0][0] ans2 = f[0][i][0] ans3 = f[0][0][i];

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 100;

int r,s,p;

double f[N+10][N+10][N+10];

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "rt", stdin);

	#endif

	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--){

				double temp = i*j + i*k + j*k;

				if (i*j==0 && i*k==0 && j*k==0) continue;

				if (i) f[i-1][j][k] += f[i][j][k]*((1.0*i*k)/temp);

				if (j) f[i][j-1][k] += f[i][j][k]*((1.0*i*j)/temp);

				if (k) f[i][j][k-1] += f[i][j][k]*((1.0*j*k)/temp);

			}

	double ans1 = 0,ans2 = 0,ans3 = 0;

	for (int i = 1;i <= r;i++) ans1+=f[i][0][0];

	for (int i = 1;i <= s;i++) ans2+=f[0][i][0];

	for (int i = 1;i <= p;i++) ans3+=f[0][0][i];

    printf("%.12f %.12f %.12f\n",ans1,ans2,ans3);

	return 0;

}

巴特西

【Codeforces Round #301 (Div. 2) D】 Bad Luck Island

最新文章

热门文章