递推过程中应该考虑的是比赛的层数,比如这样:
[盗图...]
第i个人在第k层比赛获胜的概率:dpki = ∑(dp(k - 1)i * dp(k - 1)j * pij)。
但是如何判断第i个人和第j个在第k层相遇是否合法呢,即是否在同一个子树中?
这篇博客的方法很巧妙:POJ 3071 Football(概率问题) - 窝不是爱酱,喵~~~~ - 博客频道 - CSDN.NET
在第k层比赛的选手,编号(从0开始)写作二进制的第k位不会相同。
#include <iostream> #include <stdlib.h> #include <string.h> #include <stdio.h> using namespace std; #define MAXN (1 << 7) + 10 int n; double p[MAXN][130], dp[MAXN][MAXN]; int main() { // freopen("3071.in", "r", stdin); while(scanf("%d", &n) && n != -1) { int tot = (1 << n); for(int i = 0; i < tot; i++) for(int j = 0; j < tot; j++) scanf("%lf", &p[i][j]); memset(dp, 0, sizeof(dp)); for(int i = 0; i < tot; i++) dp[0][i] = 1; for(int k = 1; k <= n; k++) for(int i = 0; i < tot; i++) for(int j = 0; j < tot; j++) if(((j >> (k - 1) ) ^ 1) == (i >> (k - 1))) dp[k][i] += dp[k - 1][i] * dp[k - 1][j] * p[i][j]; int ans = 0; for(int i = 0; i < tot; i++) if(dp[n][i] > dp[n][ans]) ans = i; printf("%d\n", ans + 1); } return 0; }