贝壳找房2021届校招算法卷3[编程题]世界杯

直接dp即可.

#include <bits/stdc++.h>
using namespace std;
const int N=2e3,M=12;
double f[N][M];//第i个人在第j轮生出的概率. 
double F[N][N];//第i名战胜第j名的概率. 
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int K=(1<<n);
    for(int i=1;i<=K;i++)
        for(int j=1;j<=K;j++)
        {
            int x;scanf("%d",&x);
            F[i][j]=(double)x/(double)100;
        }
    for(int i=1;i<=K;i++)
    {
        if(i&1) f[i][1]=F[i][i+1];
        else    f[i][1]=F[i][i-1];
    }
    for(int i=2;i<=n;i++)
    {
        int pos=(1<<i);
        for(int j=1;j<=K;j++)
        {
            for(int k=1;k<=K;k++)
            {
                if((j-1)/pos==(k-1)/pos)
                {
                    if((k-1)/(pos/2)!=(j-1)/(pos/2))
                    {
                        f[j][i]+=f[j][i-1]*f[k][i-1]*F[j][k];
                    }
                }
            }
        }
    }printf("%.10f\n",f[m][n]);
    return 0;
}