POJ 3071 Football

4 years ago

source link: https://blog.woshiluo.com/1783.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

POJ 3071 Football

2020年9月24日2020年12月16日 by woshiluo

1 题目大意

给定 2n 个整数，从 1 到 2n 编号

给定 pi,j(1≤i≤n,1≤j≤n)

定义一次操作为

选中 2k 和 2k+1 ( 0≤k,k∈Z,2k+1≤n )
其中有 p2k,2k+1 的概率选中 2k
其中有 p2k+1,2k 的概率选中 2k+1

把所有选择的数字组成一个新的数列，大小为 n2

显然最后会只剩 1 个数字

问剩哪个数字的概率最大

这东西显然是个满二叉树，大力 dfs，每次分成两半

每次向上的时候，把两边概率和一下，就没事了

3 Code

#include <cstdio>

const int N = 1100;

int n;
double p[N][N];
double f[N];

void dfs( int left, int rig ) {
    if( left == rig ) {
        f[left] = 1;
        return ;
    }
    int mid = ( left + rig ) >> 1;
    dfs( left, mid );
    dfs( mid + 1, rig );

    double la[N];
    for( int i = left; i <= rig; i ++  )
        la[i] = f[i];

    for( int i = left; i <= mid; i ++ ) {
        double cur = f[i];
        f[i] = 0;
        for( int j = mid + 1; j <= rig; j ++ ) {
            f[i] += ( cur * la[j] * p[i][j] );
        }
    }
    for( int i = mid + 1; i <= rig; i ++ ) {
        double cur = f[i];
        f[i] = 0;
        for( int j = left; j <= mid; j ++ ) {
            f[i] += ( cur * la[j] * p[i][j] );
        }
    }
}

int main() {
#ifdef woshiluo
    freopen( "poj.3071.in", "r", stdin );
    freopen( "poj.3071.out", "w", stdout );
#endif
    while(1) {
        scanf( "%d", &n );
        if( n == -1 ) 
            break;
        n = ( 1 << n );
        for( int i = 1; i <= n; i ++ ) {
            for( int j = 1; j <= n; j ++  ){
                scanf( "%lf" ,&p[i][j] );
            }
        }

        dfs( 1, n );

        int max_id = 0;
        for( int i = 1; i <= n; i ++ ) {
            if( f[i] > f[ max_id ] )
                max_id = i;
        }

        printf( "%d\n", max_id );
    }
}

class OI

local_offer 概率

POJ 3071 Football无评论

Recommend