LINK
题目
题目大意
有 n 场比赛, 2 n 2^n 2n 支队伍,给出两两队伍之间比赛的胜率。问:哪个队伍成为冠军的概率最大。
思路
概率dp从前往后推
d
p
[
i
]
[
j
]
:
dp[i][j]:
dp[i][j]:第
j
j
j个队伍在第
i
i
i场获胜的概率
求其获胜概率可以推出式子:
d
p
[
i
]
[
j
]
+
=
d
p
[
i
−
1
]
[
j
]
∗
d
p
[
i
−
1
]
[
k
]
∗
a
[
j
]
[
k
]
dp[i][j]+=dp[i-1][j]*dp[i-1][k]*a[j][k]
dp[i][j]+=dp[i−1][j]∗dp[i−1][k]∗a[j][k]
含义为在第
i
i
i场
j
j
j获胜的概率为在
i
i
i的前一场
j
j
j获胜的概率
∗
*
∗在
i
i
i的前一场
k
k
k获胜的概率
∗
j
*j
∗j与
k
k
k比赛时
j
j
j获胜的概率
二进制运用:
由于此时比赛过的队伍不能重复,所以运用二进制将其按顺序比赛
(j>>(i-1))==(k>>(i-1)^1)
第1场看其最低位不同且比最低位大的其它位相同的打比赛
第2次看其次低位不同且比最次位大的其它位相同的打比赛
……(可以自己模拟一下)
代码
#include<iostream>
using namespace std;
#define ll long long
//#define int long long
const int N = 1e5+10;
const double eps=1e-8;
double dp[150][150];//j在第i场获胜的概率
double a[150][150];//i和j比赛i获胜的概率
signed main(){
// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;
while(scanf("%d",&n)){
if(n==-1)break;
int num=1<<n;
for(int i=0;i<num;i++){
for(int j=0;j<num;j++){
scanf("%lf",&a[i][j]);
}
}
for(int i=0;i<num;i++)dp[0][i]=1;//由于乘法,初始化为1
for(int i=1;i<=n;i++){//比赛场次
for(int j=0;j<num;j++){//获胜队伍
dp[i][j]=0;//初始化
for(int k=0;k<num;k++){//与获胜队伍比的其他队伍
if((j>>(i-1))==(k>>(i-1)^1)){
dp[i][j]+=dp[i-1][j]*dp[i-1][k]*a[j][k];
}
}
}
}
int ans=0;
double maxx=dp[n][0];
for(int i=1;i<num;i++){
if(maxx<dp[n][i]){
maxx=dp[n][i];ans=i;
}
}
cout<<ans+1<<endl;
}
return 0;
}