CF16E Fish

? 状压DP;

? 由于\(n <= 18\),我们可以状态压缩.

? 一个二进制数第\(i\)位为1表示当前第\(i\)条鱼还活着.\(f[x]\)表示当前局面为\(x\)的概率是多少.

? 所以我们可以得出初始状态\(f[1 << n - 1] = 1\),因为刚刚开始所有鱼都活着,概率肯定为1.我们要求的状态是\(f[x]\),\(x\)中只有一个1的局面,因为只剩下一条鱼.

? 然后我们开始转移:\(f[x]\) 要从 \(f[x | (1 << i)]\)转移过来,\(x\)中第\(i\)为位0,表示第\(i\)条鱼这次被吃掉了.然后我们需要乘上发生这个事件的概率是多少,注意这里有一个坑点:我一开始只是将\(x\)中1的个数(\(num\))统计了出来,然后自然地想到这条鱼被吃的概率就是\(\frac{1}{num}\).结果一直不对,后来仔细一想,其实每两条鱼之间都会发生吃或被吃,所以这条鱼被吃的概率应该是\(\frac{1}{(num + 1){num} / 2}\).

#include <bits/stdc++.h>

using namespace std;

int n;
double f[300005], a[20][20];

int main() {

    cin >> n;
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= n; j++) cin >> a[i][j];
    f[(1 << n) - 1] = 1;
    for(int i = (1 << n) - 1;i >= 1; i--) {
        for(int j = 0;j < n; j++) {
            if(!(i & (1 << j))) {
                int k = i | (1 << j), num = 0; double tmp = 0; 
                for(int l = 0;l < n; l++) {
                    if(k & (1 << l)) tmp += a[l + 1][j + 1], num ++;
                }
                f[i] += f[k] * tmp * 1.0 / (num * (num - 1) / 2); 
                //上面的num是x中1的个数,这里的num是x | (1 << j)里面1的个数,所以稍微有点区别
            }
        }
    }
    for(int i = 0;i < n; i++) printf("%.6lf ", f[(1 << i)]);

    return 0;
}

CF16E Fish 状压DP

原文：https://www.cnblogs.com/czhui666/p/13905076.html