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

本文主要是介绍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<<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;
}

这篇关于2022年浙江理工大学校赛同步赛 C.Black and White 概率dp的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！