2022年浙江理工大学校赛同步赛 C.Black and White 概率dp

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<

含义为S的状态的下一个状态可能是:S(没有人出的和其他人都不一样，概率为\(1-\sum_i p[i]\);或者(S-(1<

ans定义为f((1<

code

#include
#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;
	for(int i=0;i>a[i];
	for(int i=0;i<(1<