本文共 1258 字，大约阅读时间需要 4 分钟。

$2^n$支球队,进行$n$场比赛

对于每场比赛,存活下来的队伍按照编号递增的顺序站成一排

第一支队伍和第二支打,第三支队伍和第四支队伍打…一此类推

$n$场比赛后只有一个队伍会取胜,你只需要输出最可能获得胜利的那支队伍即可。

定义$f[i][j]$表示第$i$轮第$j$个人存活下来的概率

设$j$在这一轮可能和$x_1,x_2...x_k$打

$f[i][j]=\frac{1}{k}\ast \sum _{l=1}^{k}f[x_l][j-1]$

但是这一轮,第$j$个人要和哪些队伍打…

↗     ↖                                    *        *                                ↗ ↖       ↗↖                               *     *      *   *                            ↗↖   ↗↖   ↗↖  ↗↖                            0  1   2  3  4   5  6   7

第$i$轮第$j$个人决斗的目标

110 111

就是从下往上第$i+1$层的根节点另一侧的所有节点

所以我们只需要判断每个节点在左侧还是右侧即可

所以把节点编号左移$i-1$位,那么第$i$位的二进制$0/1$代表左右侧

除了这一位,其他位都需要相等

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int maxn = 1009;int n;double f[maxn][maxn],p[maxn][maxn];int main(){
   	while( cin >> n&&n!=-1 )	{
   		int mx = (1<
      
       > p[i][j];		for(int i=0;i
       
        >(i-1))^1)==(k>>(i-1)) )					f[i][j] += f[i-1][j]*f[i-1][k]*p[j][k];			}		}		double maxx = f[n][0];		int index = 0;		for(int i=1;i
        
         maxx ) maxx = f[n][i],index = i; cout << index+1 << endl; }}
        
       
      
     
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/114871649 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！