poj_3071 Football（概率dp）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

直接上状态转移方程：

记dp[i][j]为第i轮比赛，第j个队伍获胜的概率。

那么初始状态下，dp[0][j]=1；//也就是第0轮比赛全都获胜

d[i][j]=sum(d[i-1][j]*d[i-1][k]*win[j][k])//也就是找到所有可能与j队在第i轮对决的k队，那么i队战胜k队的概率为：第i-1轮第j队出线的概率*第i-1轮第k支队伍出现的概率*第i轮j队打败k队的概率。将所有的k的可能取值都遍历一遍求概率和，所得结果就是d[i][j]。

其中，如何找到所有可能的k队是一个难点。

一般想法是先进行分组：

例如共8支队伍

第一轮中分组为（1，2）（3，4）（5，6）（7，8）

第二轮中分组为（（1|2），(3|4））（(5|6)，(7|8)）

因此不妨先按组号进行划分：

第一轮第1组组员有1，2；第2组有3，4；第3组有5，6；第四组有7，8；

观察可发现组号=（队号-1）>>1;

同样的在第二轮中组号=（队号-1）>>2;

那么第n轮中组号=（队号-1）>>n;

分完组只是第一步。

接下来我们知道，只有组号为相邻的两个数的队伍才可能比赛（而且这个相邻是有序的，必须满足（a,a+1）其中a为奇数）

这里应该可以按照奇偶性来判断，不过我没有尝试。而是用了另一个更简便的技巧：用异或运算来判断相邻。（异或完美的适配题目要求的这种相邻，具体见程序）

AC代码如下：

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

using namespace std;

double win[][];

double dp[][];

int main(void){

    int n;

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

        memset(dp,,sizeof(dp)) ;

        int len=<<n;

        for(int i=;i<=len;i++){

            for(int j=;j<=len;j++)

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

        }

        for(int i=;i<=len;i++){//初始化

            dp[][i]=;

        }

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

            for(int j=;j<=len;j++){

                //自己想,怎么判断能比赛

                for(int k=;k<=len;k++) {

                    if(((k-)>>(i-))==(((j-)>>(i-))^)){//优先级 链接：https://blog.csdn.net/u013630349/article/details/47444939

                    //位移运算相当于在进行分组，异或运算则是判断相邻，而且这个相邻是正好满足题目条件的有规律的相邻 ，可以写几个数试一下。

                        dp[i][j]+=dp[i-][j]*dp[i-][k]*win[j][k];

                    }

                }

            }

        }

        double max=dp[n][];

        int ans=;

        for(int i=;i<=len;i++){

            if(dp[n][i]>max){

                max=dp[n][i];

                ans=i;

            }

        }

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

    }

    return ;

}