[概率dp] poj 3071 Football

题目分析

    队伍编号从0~2n， dpij 代表进行i轮后，编号为j的队伍获胜的概率。

     dpij=∑k∈Sijdp(i−1)kdp(i−1)kajk ，其中 Sij 为第i轮j可能遇到的队伍的集合（这个概率dp其实就是模拟了比赛n轮）

    第i轮j可能遇到的队伍，是看队伍编号的二进制中2i位不同，2i+1到2n位相同的，可以用位运算判断。

代码

#include <cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
const int MAXN = (<<)+;
int n,m;
double a[MAXN][MAXN];
double dp[MAXN][MAXN];//别用滚动数组
int main()
{
    while(scanf("%d",&n),~n)
    {
        m = n;
        n = (<<n);
        for(int i = ; i < n; i++)
            for(int j = ; j < n; j++) scanf("%lf",&a[i][j]);
        for(int i = ; i < n; i++) dp[][i] = ;
        for(int turn = ; turn < m; turn++)
        {
            for(int i = ; i < n; i++)
            {
                double sum = ;
                for(int j = ; j < n; j++)
                    if(((i>>turn)^)==(j>>turn)) sum += dp[turn][j]*a[i][j];
                dp[turn+][i] = dp[turn][i]*sum;
//                printf("turn:%3d %d %f \n",turn+1,i,dp[i]);
            }
        }
        double maxp=;
        int ans;
        for(int i = ; i < n; i++)
            if(maxp < dp[m][i])
            {
                maxp = dp[m][i];
                ans = i+;
            }
//        cout<<dp[m][2]<<endl;
        cout<<ans<<endl;
    }
    return ;
}
           

自己挖的坑

1. 不要用滚动数组，因为降维后在一轮中dp[i]要用到dp[j]，dp[j]也会用到dp[i]。
2. double maxp =0一开始忘记初始化！！！而且最开始用的int！！！要用浮点数以后千万不要再写成整型了啊啊啊啊啊啊啊啊啊啊啊！！！记得初始化局部变量啊啊啊啊啊啊！！！