[機率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！！！要用浮點數以後千萬不要再寫成整型了啊啊啊啊啊啊啊啊啊啊啊！！！記得初始化局部變量啊啊啊啊啊啊！！！