题目分析

这是一个三国围棋对抗赛的胜率最大化问题。中国队可以在已知对方选手实力和出场顺序的情况下，选择最优的 $5$ 名选手和出场顺序来最大化获胜概率。

问题建模

比赛规则抽象

• 三个国家：中国（C）、韩国（K）、日本（J）
• 每队 $5$ 名选手，按 $1$ 到 $5$ 号顺序出场
• 比赛采用擂台赛形式，胜者守擂，败者淘汰
• 初始轮空队随机决定（各 $1/3$ 概率）

概率计算核心

需要计算在所有可能的中国选手组合和出场顺序下，中国队最终获胜的最大概率。

算法思路

1. 胜率矩阵构建

• a[i][j]：中国选手 $i$ 对韩国选手 $j$ ($1 \leq j \leq 5$) 和日本选手 $j-5$ ($6 \leq j \leq 10$) 的胜率
• b[i][j]：韩国选手 $i$ 对日本选手 $j$ 的胜率
• win[type][x][y]：统一胜率存储，便于状态转移

2. 状态设计

使用三维动态规划：

• f[country][i][j][k]：当中国队剩 $i$ 人、韩国队剩 $j$ 人、日本队剩 $k$ 人时，当前轮到 country 队比赛且中国队最终获胜的概率
• country = 0,1,2 分别表示中国、韩国、日本

3. 状态转移

根据当前轮次和剩余人数进行概率转移：

• 中国队比赛时：可能对阵韩国或日本选手
• 韩国队比赛时：可能对阵中国或日本选手
• 日本队比赛时：可能对阵中国或韩国选手

当某队人数为 $6$ 时（已全部淘汰），需要考虑另一方向的比赛。

代码解析

#include <bits/stdc++.h>
using namespace std;

int n;
double a[16][11];  // 中国选手对韩日选手胜率
double b[6][6];    // 韩国对日本胜率
double win[6][6][6]; // 统一胜率存储
double f[3][7][7][7]; // DP数组
double ans = 0, tot = 0;
bool use[16];      // 选手使用标记

// 搜索选择5名中国选手和出场顺序
void dfs(int p) {
    if (p > 5) {
        // 初始化：三个国家各有1/3概率轮空
        f[0][1][1][1] = f[1][1][1][1] = f[2][1][1][1] = 1.0 / 3.0;

        // 动态规划状态转移
        for (int i = 1; i <= 6; i++)
            for (int j = 1; j <= 6; j++)
                for (int k = 1; k <= 6; k++) {
                    // 中国队比赛的情况
                    if (i > 1) {
                        f[0][i][j][k] = f[1][i - 1][j][k] * win[4][k][i - 1] 
                                       + f[2][i - 1][j][k] * win[2][j][i - 1];
                        if (i == 6) // 考虑另一方向的比赛
                            f[0][i][j][k] += f[0][i][j - 1][k] * win[5][k][j - 1] 
                                           + f[0][i][j][k - 1] * win[3][j][k - 1];
                    }
                    
                    // 韩国队比赛的情况
                    if (j > 1) {
                        f[1][i][j][k] = f[0][i][j - 1][k] * win[5][k][j - 1] 
                                       + f[2][i][j - 1][k] * win[0][i][j - 1];
                        if (j == 6)
                            f[1][i][j][k] += f[1][i - 1][j][k] * win[4][k][i - 1] 
                                           + f[1][i][j][k - 1] * win[1][i][k - 1];
                    }
                    
                    // 日本队比赛的情况
                    if (k > 1) {
                        f[2][i][j][k] = f[0][i][j][k - 1] * win[3][j][k - 1] 
                                       + f[1][i][j][k - 1] * win[1][i][k - 1];
                        if (k == 6)
                            f[2][i][j][k] += f[2][i - 1][j][k] * win[2][j][i - 1] 
                                           + f[2][i][j - 1][k] * win[0][i][j - 1];
                    }
                }

        // 计算中国队总获胜概率
        tot = 0;
        for (int i = 1; i <= 5; i++)
            tot += f[1][i][6][6];  // 韩国、日本全淘汰的情况
        
        ans = max(ans, tot);
        return;
    }

    // 枚举选择第p个出场的中国选手
    for (int l = 1; l <= n; l++) {
        if (!use[l]) {
            use[l] = 1;
            
            // 设置该选手对韩国、日本选手的胜率
            for (int r = 1; r <= 5; r++) {
                win[0][p][r] = a[l][r];        // 中国p号 vs 韩国r号
                win[2][r][p] = 1.0 - a[l][r];  // 韩国r号 vs 中国p号
            }
            for (int r = 1; r <= 5; r++) {
                win[1][p][r] = a[l][r + 5];    // 中国p号 vs 日本r号
                win[4][r][p] = 1.0 - a[l][r + 5]; // 日本r号 vs 中国p号
            }
            
            dfs(p + 1);
            use[l] = 0;
        }
    }
}

int main() {
    scanf("%d", &n);
    
    // 读入中国选手胜率
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= 10; j++)
            scanf("%lf", &a[i][j]);
    
    // 读入韩国对日本胜率
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 5; j++) {
            scanf("%lf", &b[i][j]);
            win[3][i][j] = b[i][j];    // 韩国i号 vs 日本j号
            win[5][j][i] = 1.0 - b[i][j]; // 日本j号 vs 韩国i号
        }
    
    dfs(1);
    printf("%.6lf", ans);
    return 0;
}

胜率矩阵说明

win[type][x][y] 含义：

• type=0：中国 $x$ 号 vs 韩国 $y$ 号
• type=1：中国 $x$ 号 vs 日本 $y$ 号
• type=2：韩国 $x$ 号 vs 中国 $y$ 号
• type=3：韩国 $x$ 号 vs 日本 $y$ 号
• type=4：日本 $x$ 号 vs 中国 $y$ 号
• type=5：日本 $x$ 号 vs 韩国 $y$ 号

算法流程

1. 输入处理：读取中国选手胜率和韩日对战胜率
2. 搜索枚举：用 DFS 枚举所有 $5$ 名中国选手的组合和出场顺序
3. 动态规划：对每种组合计算中国队获胜概率
4. 结果输出：输出最大获胜概率

复杂度分析

• 组合数：$A_n^5 = n \times (n-1) \times \cdots \times (n-4)$
• DP复杂度：$O(6^3) = O(216)$ 状态，常数时间
• 总复杂度：$O(n^5 \times 216)$，在 $n \leq 15$ 时可接受

算法优势

• 全面枚举：通过 DFS 确保找到最优选手组合
• 概率建模准确：完整模拟三国擂台赛的所有可能情况
• 状态设计巧妙：通过三维 DP 精确计算获胜概率

该解法通过搜索与动态规划的结合，在可行时间内找到了中国队的最优策略。