| ||||||||||
| 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