http://acm.zstu.edu.cn/problem.php?id=4664
读完题就能发现这是一道概率dp题,那么转移方程要怎么写呢?
我首先想到了用f[i]表示还剩下i个人时游戏的期望次数,然而这个状态因为不唯一,可能在转移的过程中重复计算(例如n=3,000->001->011, 000->010->011)
再一次地仔细读题后 在李老师的提示下 ,我发现了n的范围很小(n<=20),时间足够我们枚举出游戏过程中的所有状态,所以1-n号小朋友的状态就是我们转移方程中的变量
我们用p[i]表示第i个小朋友出局的概率(当且仅当他出的颜色和其他人不一样时),可以在O(n)时间算出来
f[i]表示当前状态为i时的游戏期望次数
转移方程
\(f[S]=(1-\sum_i p[i])f[S]+\sum_i(p[i]*f(S-(1<<i)))+1\)
含义为S的状态的下一个状态可能是:S(没有人出的和其他人都不一样,概率为\(1-\sum_i p[i]\);或者(S-(1<<i)),第i个小朋友和其他人不一样而出局,概率为p[i]
ans定义为f((1<<n)-1),用dfs即可求解
code
#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 2000005; int n,t; double a[22],f[N]; double dfs(int S){ if(f[S]!=-1) return f[S]; ll sum=0,x=S; ll g[23]; for(int i=0;i<n;i++){ g[i]=x%2; x/=2; sum+=g[i]; } if(sum==2){ f[S]=0; return 0; } double p=1,q=1; // for(int i=0;i<n;i++){ if(g[i]!=0){ p*=a[i]; q*=(1-a[i]); } } double ps=0; double pro[22]={0}; //注意!!这里的pro变量一定要定义成局部变量,如果定义成全局变量然后每次dfs前初始化是错的,因为往下dfs时这个pro值被修改了,但这一层的pro值还要继续使用 for(int i=0;i<n;i++){ if(g[i]==1){ pro[i]+=p/a[i]*(1-a[i]); pro[i]+=q/(1-a[i])*a[i]; ps+=pro[i]; } } double tem=1; for(int i=0;i<n;i++){ if(g[i]==0) continue; tem+=pro[i]*dfs(S-(1<<i)); } f[S]=tem/ps; return f[S]; } int main(){ cin>>n; for(int i=0;i<n;i++) cin>>a[i]; for(int i=0;i<(1<<n);i++) f[i]=-1; double ans=dfs((1<<n)-1); printf("%.8f\n",ans); return 0; }