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 |
概率水题,内含正确代码// // Created by Artist on 2021/7/18. // #include<cstdio> using namespace std; const int maxn = 300; double a[maxn][maxn]; double dp[2][maxn]; // 某人活到现在的概率() int main(){ int n; while(~scanf("%d",&n)&&n!=-1){ int sm = (1<<n); for(int i=1;i<=sm;++i){ for(int j=1;j<=sm;++j){ scanf("%lf",&a[i][j]); } } for(int i=1;i<=sm;++i) dp[0][i] = 1,dp[1][i]=0; int flg = 0; for(int i=1;i<=n;++i){ // 自底向上更新 int sz = (1<<i); // 包有多大 for(int st=1;st<=sm;st+=sz){ // 每个包的起始位置 // 枚举任意两个包 // 跟对面那个跑就行了 for(int j=st;j<st+(sz>>1);++j){ for(int k=st+(sz>>1);k<st+sz;++k){ dp[flg^1][j] += dp[flg][j] * dp[flg][k] * a[j][k]; dp[flg^1][k] += dp[flg][k] * dp[flg][j] * a[k][j]; } } } // for(int j=1;j<=sm;++j) cout<<dp[flg^1][j]<<" "; // cout<<endl; for(int j=1;j<=sm;++j) dp[flg][j] = 0; flg^=1; } int ans; double mx=0; for(int i=1;i<=sm;++i){ // cout<<dp[flg][i]<<endl; if(dp[flg][i]>mx) mx = dp[flg][i],ans=i; } printf("%d\n",ans); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator