Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

概率水题,内含正确代码

Posted by IcecreamArtist at 2021-07-18 23:02:51 on Problem 3071
//
// 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator