POJ3071題解(機率dp)

POJ3071題解

題意

給定正整數n，共有2^n支球隊，按照二分順序比賽，給定球隊i對球隊j的勝率，問哪隻球隊有最大幾率獲勝。

箋釋

這道題還是很好的展現了動态機率思想。

從最樸素的想法來說，P[球隊i獲勝]=P[球隊i赢第1局]P[球隊i赢第2局]…*P[球隊i赢第n局]

球隊i赢第1局的機率根據資料可直接獲得，來考慮球隊i赢第j局的機率。

設dp[i][j]為在第i輪球隊j獲勝的機率。

dp[i][j]+=dp[i-1][j]*dp[i-1][rival[i][j][k]]*P[j][rival[i][j][k]]
           

其中rival[i][j][k]意為在第i輪球隊j的第k個對手，分析可知k=2^i-1，隻需要預處理出rival矩陣然後就能順利進行dp。

完整代碼

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 150
using namespace std;
int rival[][MAXN][MAXN/],n;
double P[MAXN][MAXN];
double dp[][MAXN];
void init(int s,int e,int tn)
{
    if(tn==)
    {
        return;
    }
    if(s==e)
    {
        return;
    }
    //在第2輪 對手有2種可能性
    //在第tn輪 對手有2^n-1種可能性
    int mid=(s+e)/;
    //mid定義為中間分開的前面一個
    int m=pow(,tn-);
    for(int i=s;i<=mid;i++)
    {
        for(int j=;j<=m;j++)
        {
            rival[tn][i][j]=mid+j;
           // printf("%d %d %d %d\n",tn,i,j,e/2+j);
        }
    }
    init(s,mid,tn-);
    for(int i=mid+;i<=e;i++)
    {
        for(int j=;j<=m;j++)
        {
            rival[tn][i][j]=s+j-;
        }
    }
    init(mid+,e,tn-);
}
int main()
{
    while(scanf("%d",&n),n!=-)
    {
        memset(dp,,sizeof(dp));
        int m=pow(,n);
        for(int i=;i<=m;i++)
        {
            for(int j=;j<=m;j++)
            {
                scanf("%lf",&P[i][j]);
               // printf("%d %d %f\n",i,j,P[i][j]);
            }
        }
        init(,m,n);
        for(int i=;i<=m;i++)
        {
           // printf("%d %d %f\n",i,rival[1][i][1],P[i][rival[1][i][1]]);
            dp[][i]=P[i][rival[][i][]];
        }
        for(int i=;i<=n;i++)
        {
            int l=pow(,i-);
            for(int j=;j<=m;j++)
            {
                for(int k=;k<=l;k++)
                {
                   dp[i][j]+=dp[i-][j]*dp[i-][rival[i][j][k]]*P[j][rival[i][j][k]];
                }
            }
        }
        double ansx=;
        int ansi=;
        for(int i=;i<=m;i++)
        {
            if(dp[n][i]>ansx)
            {
                //printf("%f %d\n",dp[n][i],i);
                ansx=dp[n][i];
                ansi=i;
            }
        }
        printf("%d\n",ansi);
    }
}