Problem F Codeforces 16E
这道题是一道数位Dp将鱼的死活列为0两种状态然后找DP关系
•题意:有n(n<=18)条鱼,接下来的n-1天,每天会有一对鱼(a,b)相遇,每天任意一对鱼相遇的概率是相等的,相遇之后,他们其中的一条会吃掉另外一条。•鱼a吃掉鱼b的概率是p,那么鱼b吃掉鱼a的概率就是1-p;•给你一个n*n的矩阵,表示n条鱼中的某对相遇时,互相吃掉对方的概率。•数据保证pij+pji=1;•计算每只鱼最后存活下来的概率。•status{x1,x2,x3,x4,………xn-1,xn}表示每只鱼是否还活着的状态•xi=1表示第i条鱼还活着•xi=0表示第i条鱼已经被吃掉了•dp(status)表示形成status这种状态的概率•那么刚开始的时候(第一天),所有的鱼都活着。•那么dp({1,1,1,1….,1,1,1})=1。•
•假设当前状态status活着的鱼有t条•此时,如果鱼j活着,鱼k也活着,那么j把k吃掉的概率是多少呢?•P(j吃掉k)=P(j,k相遇)*P(相遇时j可以吃掉k)=1/C(t,2)*P(相遇时j可以吃掉k)•dp(newstatus) += P(j吃掉k)*dp(status)•newstatus:j吃掉k之后的新状态 题目链接:
http://codeforces.com/problemset/problem/16/E 题目代码:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; double dp[<<];
double map[][];
int bitCount(int n)//数位上的组合数,将n转化成进制,来看里面有多少个,代表有多少条鱼
{
int cnt=;
while(n){
if(n&) cnt++;
n>>=;
}
return cnt;
} int main()
{
int n,t;
while(scanf("%d",&n)!=EOF){
memset(dp,,sizeof(dp));
for(int i=;i<n;i++)
for(int j=;j<n;j++)
scanf("%lf",&map[i][j]);
dp[(<<n)-]=1.000000;
for(int i=(<<n)-;i>=;i--){
t=bitCount(i);
if(t==) continue;
for(int j=;j<n;j++){
if((<<j)&i){
for(int k=;k<n;k++){
if((<<k)&i)
dp[i^(<<k)]+=*dp[i]/t/(t-)*map[j][k];
}
}
}
}
for(int i=;i<n;i++) printf("%0.6f ",dp[<<i]);
printf("\n");
}
return ;
}