题目大意：两个人玩牌，他们各有m(<=100)张牌，输入牌上的数字(<=50)，有n(<=50)轮回合，每回合他们从自己牌中随机选1张，牌上的数字加入答案后放回牌组中。问n回合后第一个人赢的概率是多少（保留6位小数）？
我当时居然还想随机模拟最后输出答案（显然精度不够），然而随机数生成我用的是rand*rand()，搞得分布都不均了（降智打击）
别的不管，这肯定是一道dp题，考虑到数据范围，我们可以这样设计状态。
\(A[i][j]\)表示第一个人在第i轮选到的牌的总和是j的概率，\(B[i][j]\)是第二个人的。
由于每轮我们抽到每张牌的概率是均等的，所以我们可以用 (上一轮的状态+每张卡的值)/m 来更新当前状态。
然后我们用\(sb[i]\)来表示第二个人总和小于i的概率，\(sb[i]=sb[i-1]+B[n][i-1]\)，最后枚举i，将\(A[n][i]\times sb[i]\)累加进答案。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include<cstdio> #include<iostream> #include<cstring> using namespace std; int m,n,a[100],b[100],mxa,mxb; double A[51][2501],B[51][2501]; double sb[2501]; double ans; int main(){ int t; cin>>t; while(t--){ scanf("%d",&m); mxa=mxb=0;//纪录最大值，缩小枚举范围 for(int i=0;i<m;i++){ scanf("%d",&a[i]); mxa=max(mxa,a[i]); } for(int i=0;i<m;i++){ scanf("%d",&b[i]); mxb=max(mxb,b[i]); } cin>>n; memset(A,0,sizeof(A)); memset(B,0,sizeof(B)); A[0][0]=B[0][0]=1.0;//第0轮总和为0的概率肯定是1 for(int i=1;i<=n;i++){ for(int j=0;j<=mxa*(i-1);j++){ for(int k=0;k<m;k++){ A[i][j+a[k]]+=A[i-1][j]/m; } } for(int j=0;j<=mxb*(i-1);j++){ for(int k=0;k<m;k++){ B[i][j+b[k]]+=B[i-1][j]/m; } } } sb[0]=0; for(int i=1;i<=max(mxa,mxb)*n;i++)sb[i]=sb[i-1]+B[n][i-1]; ans=0.0; for(int i=0;i<=mxa*n;i++){ ans+=A[n][i]*sb[i]; } printf("%.6lf\n",ans); } return 0; } |
支持markdown，不支持LaTex
强大的dp
LaTex不支持吗？