CodeforcesBetaRound#16E.Fish(状压dp)（概率dp）

Codeforces Beta Round #16 (Div. 2 Only) E. Fish

题目链接：## 点击打开链接

题意：

有 \(n\) 条鱼，每两条鱼相遇都会有其中一只吃掉对方，现在给你一个 \(n * n\)的矩阵，表示 \(i\) 吃掉 \(j\) 的概率，最后问你每条鱼存活的概率。

题解：

最多有 \(18\) 条鱼，吃掉的概率都不一样，可以用状态压缩，设\(dp[1<种状态，最多有 \(1<<18\) 种状态。
$ dp[i]$ 表示当前鱼的状态为 \(i\) 时的概率。
那么，\(dp( i 吃掉 j ) = dp( i 和 j 同时存在) * p( i 战胜 j )的概率 * prob(i 和 j 相遇)的概率\)。

f[i - (1<f[i - (1<

#include
using namespace std;
typedef long long ll;
double prob[18][18];
double f[1<<18];
int cnt;
int main()
{
    int n;
    cin>>n;
    for(int i=0;i    {
        for(int j=0;j        {
            cin>>prob[i][j];
        }
    }
    f[(1<    for(int i=(1<0;--i)//遍历所有状态 
    {
        cnt = 0;
        for(int j=0;j        {
            if(i & (1<            {
                cnt++;
            }
        }
        for(int j=0;j        {
            if((i&(1<            
            for(int k=j+1;k            {
                if((i&(1<                //f( j 吃掉 k ) = f( j 和 k 同时存在) * f( j 战胜k) * f( j 和 k 相遇)
                //1<                f[i - (1<                f[i - (1<            }
        }
    }
    
    for(int i=0;i    {
        printf("%.6f ",f[1<    }
    printf("%.6f\n",f[1<<(n-1)]);
    return 0;
}