codeforces 16E 概率+状压dp

63 阅读 0 评论 42 点赞

我是靠谱客的博主忧心草丛，最近开发中收集的这篇文章主要介绍codeforces 16E 概率+状压dp，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

思路：

n为18.每一为为0则是鱼死了，1则是活着。

初始状态：全活着的概率为1

当前状态的鱼j杀死鱼k的概率,相遇的概率乘以j杀k的概率，累加至新状态即可。

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <stdlib.h>
#include <iomanip>
#include <fstream>

using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define maxn 105
#define MOD 1000000007
#define mem(a , b) memset(a , b , sizeof(a))
#define LL long long
#define ULL unsigned long long
#define FOR(i , n) for(int i = 1 ;  i<= n ; i ++)
typedef pair<int , int> pii;
#define INF 100000000
int n;
double a[maxn][maxn];
double dp[1<<18];

int main()
{
    while(scanf("%d" , &n) != EOF)
    {
        for(int i = 0 ; i < n ; i ++)
        {
            for(int j = 0 ; j < n ; j ++)
            {
                scanf("%lf" , &a[i][j]);
                //cout << a[i][j] << endl;
            }
        }
        mem(dp , 0);
        dp[(1<<n) - 1] = 1;
        for(int i = (1<<n) - 1 ; i >= 1 ; i --)
        {
            int num = 0 , tmp = i;
            while(tmp != 0)
            {
                if(tmp & 1) num ++;
                tmp >>= 1;
            }
            if(num == 1) continue;
            double ch = 2.0 * dp[i] / num / (num-1);
            for(int j = 0 ; j < n ; j ++)
            {
                if(i & ( 1 << j))
                {
                    for(int k = 0 ; k < n ; k ++)
                    {
                        if(i & ( 1 << k))
                        {
                            dp[i^(1<<k)] += ch * a[j][k];
                        }
                    }
                }
            }
        }

        for(int i = 0 ; i < n ; i ++)
        {
            printf("%.6lf" , dp[(1 << i)]);
            if(i != n-1) printf(" ");
        }
        cout <<endl;
    }
    return 0;
}