poj3071 Football（概率dp）

时间：2023-03-08 21:00:20

poj3071 Football

题意：有2^n支球队比赛，每次和相邻的球队踢，两两淘汰，给定任意两支球队相互踢赢的概率，求最后哪只球队最可能夺冠。

我们可以十分显然（大雾）地列出转移方程（设$f[ i ][ j ]$为第 $j$ 支球队踢赢第 $i$ 场比赛的概率，$k$为枚举的对手）：

$f[ i ][ j ] += f[ i-1 ][ j ] * f[ i-1 ][ k ] * p[ j ][ k ]$

现在问题来了：怎么枚举 k, k的范围是啥

我们先列出比赛的模型（a Tower，n=4）

　　　　　　　　　　☺

　　　　♦　　　　　　　　　　　  ♦　　　　　　 4

　　　 (♦♦) 　　　　　　　　　　 (♦♦)　　　 　　  3

　　((♦♦)  (♦♦)) 　　　　　　　 ((♦♦)  (♦♦))　　  　    2

(((♦♦)  (♦♦))  ((♦♦)  (♦♦)))  (((♦♦)  (♦♦))  ((♦♦)  (♦♦)))         1

tips：为了方便块的运算，球队编号从0开始

对于第$ i$ 场比赛的球队$ j $ ，我们先找出它在第$i-1 $场比赛中所属的块：$u= j / ( 1<<(i-1) )$

蓝后我们可以直接用异或 ^ 求出它的对手在第$ i-1 $场比赛中所属的块  u^=1

而球队$j$ 在第 $i$ 场比赛中的对手只可能在块 $u$ 内且块中的每一队都可能是对手

于是我们枚举一遍块$u$内的元素，就可以愉快地dp了

（用cin直接TLE了（大雾））

#include<iostream>

#include<cstdio>

#define re register

using namespace std;

int n,m,ans;

double f[][],p[][],mxd;

int main(){

    while(scanf("%d",&n)!=EOF){

        if(n==-) break;

        m=<<n;

        for(re int i=;i<m;++i)

            for(re int j=;j<m;++j)

                scanf("%lf",&p[i][j]);

        re int u;

        for(u=;u+<m;u+=){ //初始化

            f[][u]=;

            f[][u+]=;

            f[][u+]=;

            f[][u+]=;

        }for(;u<m;++u) f[][u]=; //循环展开

        for(re int i=;i<=n;++i)

            for(re int j=;j<m;++j){

                u=j/(<<(i-)); u^=;

                u*=(<<(i-));

                f[i][j]=;

                for(re int k=u+(<<(i-))-;k>=u;--k) //枚举块u内的所有球队

                    f[i][j]+=f[i-][j]*f[i-][k]*p[j][k];

            }

        mxd=;

        for(re int i=;i<m;++i)

            if(f[n][i]>mxd)

                mxd=f[n][i],ans=i;

        printf("%d\n",ans+);

    }return ;

}

相关文章