1 题目大意

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

给定 $p_{i,j}(1\leq i \leq n, 1 \leq j \leq n)$

定义一次操作为

选中 $2k$ 和 $2k+1$ ( $0 \leq k, k \in Z, 2k+1 \leq n$ )
其中有 $p_{2k,2k+1}$ 的概率选中 $2k$
其中有 $p_{2k+1,2k}$ 的概率选中 $2k+1$

把所有选择的数字组成一个新的数列，大小为 $\frac{n}{2}$

显然最后会只剩 $1$ 个数字

问剩哪个数字的概率最大

2 思路

这东西显然是个满二叉树，大力 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 );
    }
}