poj

http://poj.org/problem?id=3071

参考博客：http://blog.csdn.net/libin56842/article/details/10054725

不得不说概率dp很难理解！！

这题最主要的就是判断是否相邻,可以用位运算找规律求出.

p,q得到的是每一轮0-m-1个球队的位置.因为球队标号是从0开始的,如果是奇数位置就要和前面一个队伍比赛,

如果是偶数位置就要和后面一个队伍比赛.每次增加一轮p和q的取值范围会缩小一倍.也就是说会减少一半的队伍.

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 double dp[150][150],a[150][150];
 5 int main()
 6 {
 7     //freopen("a.txt","r",stdin);
 8     int n,m;
 9     while(~scanf("%d",&n),n+1)
10     {
11         m=1<<n;
12         for(int i=0;i<m;i++)
13             for(int j=0;j<m;j++) scanf("%lf",&a[i][j]);
14         memset(dp,0,sizeof(dp));
15         for(int i=0;i<m;i++) dp[0][i]=1; //初始赢的概率都是1 
16         for(int i=1;i<=n;i++)
17         {
18             for(int j=0;j<m;j++)
19             {
20                 for(int k=0;k<m;k++)
21                 {
22                     int p=k>>(i-1),q=j>>(i-1); //得到 两只球队的位置编号 
23                     //printf("%d %d
",p,q);
24                     if(p&1)  //是奇数
25                     {
26                         p--; //判断是否相邻
27                         if(p==q)
28                         {   //i-1轮j存活,k存活,第i轮j赢k
29                             dp[i][j]+=dp[i-1][j]*dp[i-1][k]*a[j][k];
30                         }
31                     }
32                     else
33                     {
34                         p++;
35                         if(p==q)
36                         {
37                             dp[i][j]+=dp[i-1][j]*dp[i-1][k]*a[j][k];
38                         }
39                     }
40                 }
41             }
42         }
43         int ans=0;
44         for(int i=0;i<m;i++)
45         {
46             if(dp[n][i]>dp[n][ans])
47                 ans=i;
48         }
49         printf("%d
",ans+1);
50     }
51     return 0;
52 }