1.题目描述：点击打开链接
2.解题思路：本题利用概率dp解决。一开始想着如何推出每一个最终的概率公式，没有思路。最后发现其实可以通过概率dp解决。设状态d(i,j,k)为还有i个石头，，j个剪刀，k个布时的概率，那么不难得到以下三个递推式：
d(i-1,j,k)+=d(i,j,k)*(i*k)/(i*j+i*k+j*k);
d(i,j-1,k)+=d(i,j,k)*(i*j)/(i*j+i*k+j*k);
d(i,j,k-1)+=d(i,j,k)*(j*k)/(i*j+i*k+j*k);
由于题目中i,j,k的最大范围只是100，可以直接用O(N*3)计算出所有的状态，最终的答案为ans=sum{d(i,0,0)|1≤i≤r}（后两种类似）。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;typedef long long ll;#define me(s) memset((s),0,sizeof(s))#define For(i,n) for(int i=1;i<=(n);i++)#define N 100+5double dp[N][N][N];int main(){//freopen("t.txt", "r", stdin);int r, s, p;while (cin >> r >> s >> p){memset(dp, 0, sizeof(dp));dp[r][s][p] = 1.0;for (int i = r; i >= 0;i–)for (int j = s; j >= 0;j–)for (int k = p; k >= 0;k–)if ((i&&j)||(j&&k)||(k&&i)){double tot = i*j + i*k + j*k;if (k)dp[i][j][k – 1] += dp[i][j][k] * (double)j*k / tot;if (j)dp[i][j – 1][k] += dp[i][j][k] * (double)i*j / tot;if (i)dp[i-1][j][k] += dp[i][j][k] * (double) i*k / tot;}double s1, s2, s3;s1 = s2 = s3 = 0.0;For(i, r)s1 += dp[i][0][0];For(i, s)s2 += dp[0][i][0];For(i, p)s3 += dp[0][0][i];printf("%.12lf %.12lf %.12lf\n", s1, s2, s3);}return 0;}
你说只有有缘人才可以取下，我看着你手中的戒指，
