计算机牛牛要参加一场程序猿世界杯，一共有名选手参加比赛，选手们依次编号从到，比赛采用单淘汰制，即第一轮进行比赛，第一轮的决胜者再与相连的选手进行比赛，每轮都会淘汰一半的选手，进行之后能决出冠军。牛牛的编号为，但是牛牛知道了各个选手与其他选手比赛时的胜率。牛牛想知道他能夺冠的概率是多少呢，牛牛给你各个选手之间若进行比赛时的胜率，请你告诉牛牛他夺冠可能的概率是多少呢-笔试面试资料

牛牛要参加一场程序猿世界杯，一共有名选手参加比赛，选手们依次编号从到，比赛采用单淘汰制，即第一轮进行比赛，第一轮的决胜者再与相连的选手进行比赛，每轮都会淘汰一半的选手，进行之后能决出冠军。牛牛的编号为，但是牛牛知道了各个选手与其他选手比赛时的胜率。牛牛想知道他能夺冠的概率是多少呢，牛牛给你各个选手之间若进行比赛时的胜率，请你告诉牛牛他夺冠可能的概率是多少呢

肖战公关团队

暴力及记忆化搜索。 代表第 个人赢了 场的概率，总时间复杂度 。

#include <bits/stdc++.h>  int n, m; double dp[1 << 10][11]; double win_rate[1 << 10][1 << 10];  double dfs(int who, int times, int l, int r) {   if (dp[who][times] > -0.5) {     return dp[who][times];   }   int mid = (l + r) >> 1;   if (who > mid) {     double ans = dfs(who, times - 1, mid + 1, r), t = 0.0;     for (int i = l; i <= mid; i++) {       t += dfs(i, times - 1, l, mid) * win_rate[who][i];     }     dp[who][times] = ans * t;     return dp[who][times];   } else {     double ans = dfs(who, times - 1, l, mid), t = 0.0;     for (int i = mid + 1; i <= r; i++) {       t += dfs(i, times - 1, mid + 1, r) * win_rate[who][i];     }     dp[who][times] = ans * t;     return dp[who][times];   } }  int main() {   std::cin.sync_with_stdio(false);   std::cin.tie(nullptr);   std::cin >> n >> m;   for (int i = 0; i < (1 << n); i++) {     dp[i][0] = 1.0;     for (int j = 1; j <= n; j++) {       dp[i][j] = -1.0;     }   }   for (int i = 0; i < (1 << n); i++) {     for (int j = 0; j < (1 << n); j++) {       std::cin >> win_rate[i][j];       win_rate[i][j] /= 100.0;     }   }   std::cout << std::fixed << std::setprecision(10) << dfs(m - 1, n, 0, (1 << n) - 1) << 'n'; }

今天 12:58:09 回复(0)