POJ 3071 Football：概率dp

题目链接：http://poj.org/problem?id=3071

题意：

　　给定n，有2^n支队伍参加足球赛。

　　给你所有的p[i][j]，表示队伍i打败队伍j的概率。

　　淘汰赛制。第一轮(1,2)两队比、(3,4)比、(5,6)比...共进行n轮比赛后产生冠军。

　　问你冠军最有可能是哪支队伍。

题解：

　　表示状态：

　　　　dp[i][j] = probability to win

　　　　第i支队伍能够参加第j轮比赛的概率。

　　找出答案：

　　　　i of max dp[i][n+1]

　　　　n轮比赛后，冠军该参加第n+1轮比赛（不存在的）。

　　如何转移：

　　　　now: dp[i][j]

　　　　dp[i][j+1] = ∑ (dp[i][j] * dp[k][j] * p[i][k])　（加法原理）

　　　　k: 第j轮比赛和i比的队伍

　　　　P（i晋级到j+1轮） = ∑ (P（i晋级到j轮） * P（k晋级到j轮） * P（i打败k）)

　　　　怎样枚举k:

　　　　　　将所有队伍从0开始编号，并用二进制表示。

　　　　　　第i支战队第j轮会碰到的对手是：将i化为二进制，从右往左开始算，第j-1位会不同，第j位开始要相同，其余位任意的所有数。

　　边界条件：

　　　　dp[i][1] = 1
　　　　others = 0

　　注：本题居然卡cin。。。 (*｀皿´*)ﾉ 

AC Code:

// state expression:
// dp[i][j] = probability to win
// i: which team
// j: which round
//
// find the answer:
// i of max dp[i][n+1]
//
// transferring:
// dp[i][j+1] = sigma (dp[i][j] * dp[k][j] * p[i][k])
// 0<=t<(1<<(j-1))
// k = (((i>>(j-1))^1)<<(j-1))|t
//
// boundary:
// dp[i][1] = 1
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 10
#define MAX_T 150

using namespace std;

int n;
int ans;
double p[MAX_T][MAX_T];
double dp[MAX_T][MAX_N];

void read()
{
    for(int i=0;i<(1<<n);i++)
    {
        for(int j=0;j<(1<<n);j++)
        {
            scanf("%lf",&p[i][j]);
        }
    }
}

void solve()
{
    memset(dp,0,sizeof(dp));
    for(int i=0;i<(1<<n);i++)
    {
        dp[i][1]=1;
    }
    for(int j=1;j<=n;j++)
    {
        for(int i=0;i<(1<<n);i++)
        {
            for(int t=0;t<(1<<(j-1));t++)
            {
                int k=((((i>>(j-1))^1)<<(j-1))|t);
                dp[i][j+1]+=dp[i][j]*dp[k][j]*p[i][k];
            }
        }
    }
    double maxn=0;
    for(int i=0;i<(1<<n);i++)
    {
        if(dp[i][n+1]>maxn)
        {
            maxn=dp[i][n+1];
            ans=i+1;
        }
    }
}

void print()
{
    printf("%d
",ans);
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        if(n==-1) break;
        read();
        solve();
        print();
    }
}