CodeForces - 16E Fish(状压dp)

Posted on | In , ,

思路

简单的状压dp。令dp[i]状态中1为已死亡的鱼，0为存活的鱼，dp表示转移到这个状态的概率。dp转移方程为：

1
2
dp[state|(1<<i)]+=topro*dp[state]*pro[j][i];
dp[state|(1<<j)]+=topro*dp[state]*pro[i][j];

这个转移方程的灵感来自于全概率公式，topro表示选中这一对鱼的概率，pro表示i吃j的概率，由全概率公式可知我们把所有可能的转移概率加起来就是最终答案。

代码

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
#include <bits/stdc++.h>
#define ms(a,val) memset(a,val,sizeof(a))
#define ll long long
#define INF 0x7fffffff

using namespace std;

double dp[1<<18],pro[20][20];

int main() {
    int n;
    while(cin>>n){
        for(int i=0;i<(1<<18);i++)dp[i]=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cin>>pro[i][j];
            }
        }
        dp[0]=1;
        for(int state=0;state<(1<<n);state++){
            int tstate=state,cnt=0;
            double topro;
            while(tstate){
                if(tstate&1)cnt++;
                tstate>>=1;
            }
            if(cnt==n-1)continue;
            cnt=n-cnt;
            topro=2/(double)(cnt*(cnt-1));
            for(int i=0;i<n;i++){
                if(((state>>i)&1))continue;
                for(int j=i+1;j<n;j++){
                    if(((state>>j)&1))continue;
                    dp[state|(1<<i)]+=topro*dp[state]*pro[j][i];
                    dp[state|(1<<j)]+=topro*dp[state]*pro[i][j];
                }
            }
        }
        for(int i=0;i<n;i++){
            int temp=(1<<n)-1;
            temp^=(1<<i);
            if(i)cout<<" ";
            cout<<fixed<<setprecision(6)<<dp[temp];
        }
        cout<<endl;
    }
	return 0;
}