poj3071 Football（概率dp）

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[9][130],p[130][130],mxd;
int main(){
    while(scanf("%d",&n)!=EOF){
        if(n==-1) break;
        m=1<<n;
        for(re int i=0;i<m;++i)
            for(re int j=0;j<m;++j)
                scanf("%lf",&p[i][j]);
        re int u;
        for(u=0;u+4<m;u+=4){ //初始化
            f[0][u]=1;
            f[0][u+1]=1;
            f[0][u+2]=1;
            f[0][u+3]=1;
        }for(;u<m;++u) f[0][u]=1; //循环展开
        for(re int i=1;i<=n;++i)
            for(re int j=0;j<m;++j){
                u=j/(1<<(i-1)); u^=1;
                u*=(1<<(i-1));
                f[i][j]=0;
                for(re int k=u+(1<<(i-1))-1;k>=u;--k) //枚举块u内的所有球队
                    f[i][j]+=f[i-1][j]*f[i-1][k]*p[j][k];
            }
        mxd=0;
        for(re int i=0;i<m;++i)
            if(f[n][i]>mxd)
                mxd=f[n][i],ans=i;
        printf("%d
",ans+1);
    }return 0;
}