当前位置: 首页 > 工具软件 > Fish Sync > 使用案例 >

[luogu] CF16E Fish 状态压缩+概率dp

雍兴修
2023-12-01

前言

传送门 :

思路

题目描述显然使用状态压缩表示每条鱼是否被吃,然后再使用概率 d p dp dp计算即可

状态表示 :
d p [ s t a t e ] dp[state] dp[state] 表示当前 s t a t e state state的存活概率

状态转移 :
d p [ i ] = d p [ i ∣ ( 1 < < j − 1 ) ] ∗ p [ k ] [ j ] / ( 1.0 ∗ ( c n t + 1 ) ∗ c n t / 2.0 ) dp[i] = dp[i|(1<<j-1)]∗p[k][j]/(1.0∗(cnt+1)∗cnt/2.0) dp[i]=dp[i(1<<j1)]p[k][j]/(1.0(cnt+1)cnt/2.0)

前 一 个 的 概 率 ∗ k 吃 j 的 概 率 ∗ 选 出 j , k 的 概 率 前一个的概率*k吃j的概率*选出j,k的概率 kjj,k

也就是 C n 2 C_n^2 Cn2,因为当前状态是 c n t cnt cnt但是从上一个状态转移过来所以是 c n t + 1 cnt+1 cnt+1

Code

// Problem: CF16E Fish
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF16E
// Memory Limit: 125 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i<=b;i++)
#define Fde(i,a,b) for(int i=a;i>=b;i--)

typedef priority_queue<int,vector<int>,greater<int>>  Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> mp;
const int N = 30;
int n;
double p[N][N],dp[1<<20];
int calc(int x){
	int res = 0 ;
	while(x){
		x-=(x&-x);
		res++;
	}
	return res;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>p[i][j];
	
	//全部鱼存活的概率为 1
	dp[(1<<n)-1] = 1;
	
	for(int i=(1<<n)-2;i;i -- ){
		int cnt = calc(i);
		for(int j=1;j<=n;j++){//枚举被吃的鱼的编号
			if((i&(1<<(j-1)))) continue;//如果没有被吃 不需要考虑
			for(int k=1;k<=n;k++){
				if(!(i&(1<<(k-1)))) continue;
				dp[i]+= dp[i|(1<<(j-1))] * p[k][j]/(1.0*(cnt+1)*cnt/2.0);
			}
		}
	}
	
	for(int i =0;i <n; i++ )
	printf("%.6lf ",dp[1<<i]);
	
	
}

int main(){
    //int t;cin>>t;while(t--)
    solve();
    return 0 ;
}

 
 类似资料: