传送门
概率dp简单题。
设f[i][j]表示前i轮j获胜的概率。
如果j,k能够刚好在第i轮相遇，找规律可以发现j,k满足：
(j−1)>>(i−1)" role="presentation" style="position: relative;">(j−1)>>(i−1)(j−1)>>(i−1)^1==(k−1)>>(i−1)" role="presentation" style="position: relative;">1==(k−1)>>(i−1)1==(k−1)>>(i−1)。
简单举个例子？
假设有八个人，对应下来二进制为：000,001,010,011,100,101,110,111（注意要减一）。
对应上面的看一下应该就秒懂了。
比如说第一轮中，000和001是一组的，因为它们第0位不同，其余位相同。
然而第一轮中，001和010不是一组的，因为它们第1位也不同。
比如说第二轮中，000可以和011是一组的，因为它们第1位是不同的，且第2位相同。
但是000和110不是一组的，因为它们第2位不同。
于是就有了状态转移方程：
f[i][j]=∑j,k可以在一组f[i−1][j]∗f[i−1][k]∗p[i][j]" role="presentation" style="position: relative;">f[i][j]=∑j,k可以在一组f[i−1][j]∗f[i−1][k]∗p[i][j]f[i][j]=∑j,k可以在一组f[i−1][j]∗f[i−1][k]∗p[i][j]
解释：
前i-1轮j,k必须不输，且j必须在这一轮战胜k。
代码：
#include<iostream>
#include<cstdio>
#define N 150
using namespace std;
double p[N][N],f[N][N];
int n,len;
int main(){
while(scanf("%d",&len)){
if(len==-1)break;
n=1<<len;
for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)scanf("%lf",&p[i][j]),f[i][j]=0;
for(int i=1;i<=n;++i)f[0][i]=1;
for(int k=1;k<=len;++k){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if((((i-1)>>(k-1))^1)==((j-1)>>(k-1)))
f[k][i]+=f[k-1][i]*f[k-1][j]*p[i][j];
}
}
}
double ans=0;
int pos=0;
for(int i=1;i<=n;++i)if(ans<f[len][i])ans=f[len][i],pos=i;
printf("%d\n",pos);
}
return 0;
}