亚瑟王游戏期望伤害 题解

问题分析

我们有 $n$ 张卡牌，进行 $r$ 轮游戏。每轮从第一张卡开始依次尝试发动技能，一旦某张卡发动技能就结束该轮。求总伤害的期望值。

关键观察

1. 期望的线性性

总伤害期望 = 每张卡牌造成的伤害期望之和：

$$E = \sum_{i=1}^n E_i$$

其中 $E_i$ 是第 $i$ 张卡牌在整个游戏中造成伤害的期望。

2. 第 $i$ 张卡发动技能的条件

第 $i$ 张卡要在某轮中发动技能，需要满足： 在前面的轮次中，第 $i$ 张卡之前的所有卡牌都没有发动技能

在该轮中，第 $i$ 张卡之前的卡牌在该轮没有发动技能

第 $i$ 张卡在该轮成功发动技能

算法思路

动态规划状态设计

定义 $f[i][j]$ 表示考虑前 $i$ 张卡牌，还剩 $j$ 轮游戏时，后续游戏的期望伤害。

状态转移考虑第 $i$ 张卡牌在当前轮次是否发动技能：

如果第 $i$ 张卡发动技能：造成 $d_i$ 点伤害，结束当前轮

如果第 $i$ 张卡没有发动技能：继续考虑下一张卡牌

代码中的实现

struct node {
    double Pr, Ex;  // Pr: 概率权重, Ex: 条件期望
    // 重载运算符实现概率混合
};

double solve(int n, int r) {
    // 初始化：f[0][r] = 1，其他为0
    for (int i = 1; i <= n; i++) {
        double pw = 1;  // (1-p_i)^k，前k轮都不发动的概率
        for (int j = 1; j <= r; j++) {
            pw *= (1 - p[i]);  // 更新连续不发动的概率
            // 状态转移
            f[i][j] += pw * f[i-1][j];           // 当前轮不发动
            f[i][j-1] += (1 - pw) * f[i-1][j] + d[i]; // 当前轮发动
        }
    }
}

状态转移方程

设 $P_i$ 为第 $i$ 张卡的发动的概率，则：

$$f[i][j] = \sum_{k=0}^j (1-P_i)^k P_i \cdot (d_i + f[i-1][j-k]) + (1-P_i)^{j+1} \cdot f[i-1][0] $$

复杂度分析

• 时间复杂度：$O(n \times r)$，其中 $n \leq 220$，$r \leq 132$
• 空间复杂度：$O(r)$，使用滚动数组优化

样例验证

对于样例输入：

n=3, r=2
卡牌1: p=0.5, d=2
卡牌2: p=0.3, d=3  
卡牌3: p=0.9, d=1

算法计算过程：

1.初始化 $f[0][2] = 1$

2.处理第1张卡牌，考虑2轮游戏

3.处理第2张卡牌，更新期望

4.处理第3张卡牌，得到最终期望 $3.266025$

输出：3.2660250000

精度处理

使用 double 类型存储概率和期望

输出10位小数保证精度

相对误差要求 $10^{-8}$

关键技巧

1.概率混合：使用自定义的 node 结构体处理概率权重和条件期望

2.滚动数组：节省空间，只保留当前和上一层的状态

3.连续失败概率：用 $pw$ 累积连续不发动技能的概率

4.期望线性性：将总期望分解为每张卡的贡献

总结

本题通过动态规划方法，巧妙地计算了在复杂游戏规则下的期望伤害。算法利用概率论中的期望线性性，将问题分解为每张卡牌的贡献，并通过状态转移高效计算。在给定的数据范围内，算法能够快速准确地计算出结果。