Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
考察位运算和DP#include"iostream" #include"cstdio" #include"cstring" using namespace std; const int ms=130; double p[ms][ms]; double dp[ms][8]; int main() { int n,i,j; while(scanf("%d",&n),n!=-1) { int m=(1<<n); for(i=0;i<m;i++) { for(j=0;j<m;j++) scanf("%lf",&p[i][j]); dp[i][0]=1; } int ans; for(i=0;i<n;i++) { ans=0; for(j=0;j<m;j++) { double sum=0; for(int k=(1<<i);k<(1<<(i+1));k++) { sum+=dp[k^j][i]*p[j][k^j]; } dp[j][i+1]=dp[j][i]*sum; if(dp[j][i+1]>dp[ans][i+1]) ans=j; } } printf("%d\n",ans+1); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator