2 0 0.5 0.5 0 3 0 1 1 0 0 0.5 0 0.5 0
0.500 0.5001.000 0.000 0.000
状压DP:DP[S]代表状态为S的时候活着的概率。
相应位的二进制数:1代表活着。0代表死了。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<limits.h> typedef long long LL; using namespace std; int n; double p[18][18]; double dp[1<<18]; int main() { while(~scanf("%d",&n)) { int t=(1<<n)-1; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) scanf("%lf",&p[i][j]); } memset(dp,0,sizeof(dp)); dp[t]=1.0; for(int i=t;i>0;i--) { int cnt=0; for(int k=0;k<n;k++) { if(i&(1<<k)) cnt++; } // cout<<"1111 "<<i<<" "<<cnt<<endl; int total=cnt*(cnt-1)/2; if(!total) continue; for(int j=0;j<n;j++) { if(((1<<j)&i)==0) continue; for(int k=j+1;k<n;k++) { if(((1<<k)&i)==0) continue; dp[i^(1<<j)]+=dp[i]*p[k][j]/total; dp[i^(1<<k)]+=dp[i]*p[j][k]/total; } } } for(int i=0;i<n;i++) { if(i==n-1) printf("%.3f\n",dp[1<<i]); else printf("%.3f ",dp[1<<i]); } } return 0; }
原文:http://blog.csdn.net/u013582254/article/details/39743429