POJ 3071 Football【概率DP】

题目链接

http://poj.org/problem?id=3071

思路

概率DP，方程本身很简单，设

dp[i][j]

为第i支队伍撑过第j轮的概率。

则对第j轮i所有的可能对手k，

dp[i][j]+=dp[i][j-1]*dp[k][j-1]*p[i][k]

。

但是难点就是怎么找出可能对手k，上网搜了下发现可以巧妙的用二进制搞定。

把ijk都从0开始编号，那么在第j轮，i和k可能是对手当且仅当i和k的第(j+1)位相反且最高位相同。

即：

((k>>j)^1)==(i>>j)

。

AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;


double dp[][];
double p[][];
int main()
{
    int n;
    while(scanf("%d",&n),n!=-)
    {
        int n_team=(<<n);
        for(int i= ; i<n_team ; ++i)
            for(int j= ; j<n_team ; ++j)
                scanf("%lf",&p[i][j]);
        memset(dp,,sizeof dp);
        for(int i= ; i<n_team ; i+=)
        {
            dp[i][]=p[i][i+];
            dp[i+][]=p[i+][i];
        }
        for(int j= ; j<n ; ++j)
        {
            for(int i= ; i<n_team ; ++i)
            {
                for(int k= ; k<n_team ; ++k)
                if(((k>>j)^)==(i>>j))
                {
                    dp[i][j]+=dp[i][j-]*dp[k][j-]*p[i][k];
                }
            }
        }
        double max_p=dp[][n-];
        int max_i=;
        for(int i= ; i<n_team ; ++i)
        {
            if(dp[i][n-]>max_p)
            {
                max_p=dp[i][n-];
                max_i=i;
            }
        }
        printf("%d\n",max_i+);
    }
    return ;
}