莫娜与阿贝多 - 题解

标签与难度

标签: 动态规划, 概率DP, 逆向DP, 状态机模型难度: 2200

题目大意喵~

喵哈~！各位旅行者，我是你们的我向导，今天我们来挑战一道关于炼金术的有趣题目，喵~！

是这样的，我们有 m 个等级的物品，编号从 1 到 m。我们可以用 3 个等级为 k 的物品，合成出 1 个等级为 k+1 的物品。这个过程就像阿贝多老师在做炼金实验一样，充满了各种可能性！

每一次合成，我们都有两种配方可以选择：

稳健配方: 消耗 3 个 k 级物品，得到 1 个 k+1 级物品。有 p 的概率，系统会返还我们 1 个 k 级物品。也就是说，这次合成实际只消耗了 2 个 k 级物品！
激进配方: 消耗 3 个 k 级物品，得到 1 个 k+1 级物品。有 q 的概率，我们会“暴击”，额外多得到 1 个 k+1 级物品！也就是说，一次合成了俩，血赚！

我们一开始手里有各种等级的物品若干，数量都告诉我们啦。我们的最终目标是，通过一系列最最聪明的合成决策，得到至少 n 个最高等级（m 级）的物品。

问题就是：在我们每一步都做出最优选择（最大化成功概率）的情况下，我们达成目标的最终概率是多少呢？

解题思路分析

这道题的目标是求一个最大概率，而且每一步的决策都依赖于当前的状态（我们有多少个什么等级的物品），这有很浓的动态规划（DP）的味道，特别是概率DP，喵~

直接从低级物品往高级推（正向DP）会很麻烦，因为我们在合成 k 级物品时，不知道一个 k+1 级的物品对最终目标的“价值”有多大。一个更自然的想法是逆向DP，从最终目标开始，一步步往前倒推。

我们先来定义一下DP的状态吧！一个最直接的想法是 dp[i][c_1][c_2]...[c_m] 表示在拥有 c_1 个1级物品, c_2 个2级物品...的情况下，达成目标的最大概率。但这状态太多了，我的猫猫大脑都要过载了，肯定不行！

正确的思路是逐级分析。我们从最高级 m 级倒推到 1 级。

核心思想：定义“状态函数”

让我们定义一个“状态函数” f[i][j]，它表示：当我们开始处理第 i 级的物品时（即 1 到 i-1 级的物品还没动），如果我们手头总共有 j 个第 i 级的物品，那么我们最终能达成目标的最大概率是多少。这里的 j 个物品，包含了初始拥有的 a[i] 个，以及未来可能从更低等级合成过来的。

我们的最终答案，就是 f[1][a[1]]，因为我们一开始就拥有 a[1] 个1级物品，a[2] 个2级物品，等等。

状态转移：从 `f[i+1]` 到 `f[i]`

这是最关键的一步！假设我们已经知道了 f[i+1] 的所有值（即对于任意数量的 i+1 级物品，我们都知道成功的概率），我们如何计算出 f[i] 呢？

为了计算 f[i][j_i] (拥有 j_i 个 i 级物品的成功率)，我们需要考虑如何最优地把这 j_i 个 i 级物品和初始的 a[i+1] 个 i+1 级物品结合起来，去合成 i+2 级物品，并最终达成目标。

这本身就是一个子问题！我们可以为这个子问题再建立一个DP模型。

子问题的DP：`g[j][k]`

让我们定义一个辅助DP g[j][k]，它表示：在当前阶段（从 i 级到 i+1 级），如果我们有 j 个 i 级物品和 k 个 i+1 级物品，我们能达成的最大成功概率是多少。

这个 g[j][k] 的计算方法如下：

基本情况 (Base Case): 如果 j < 3，我们手里的 i 级物品不够3个，无法进行合成了。所以我们只能带着 k 个 i+1 级的物品进入下一阶段。这个情况下的成功概率，就等于我们已经算好的 f[i+1][k]。所以, g[j][k] = f[i+1][k] for j \in \{0, 1, 2\}.
递推情况 (Recursive Step): 如果 j >= 3，我们就有得选了！我们可以选择进行一次合成。
- 选择稳健配方 (Type 1):
  - 有 p 的概率，消耗2个 i 级物品，得到1个 i+1 级物品。状态变为 (j-2, k+1)。
  - 有 1-p 的概率，消耗3个 i 级物品，得到1个 i+1 级物品。状态变为 (j-3, k+1)。
  - 期望成功概率为: p * g[j-2][k+1] + (1-p) * g[j-3][k+1]
- 选择激进配方 (Type 2):
  - 有 q 的概率，消耗3个 i 级物品，得到2个 i+1 级物品。状态变为 (j-3, k+2)。
  - 有 1-q 的概率，消耗3个 i 级物品，得到1个 i+1 级物品。状态变为 (j-3, k+1)。
  - 期望成功概率为: q * g[j-3][k+2] + (1-q) * g[j-3][k+1]
我们当然会选择能让我们成功概率更大的那个配方！所以：
$g[j][k] = \max \left( p \cdot g[j-2][k+1] + (1-p) \cdot g[j-3][k+1], \quad q \cdot g[j-3][k+2] + (1-q) \cdot g[j-3][k+1] \right)$

连接 `g` 和 `f`

有了 g 的计算方法，我们就可以计算 f[i] 了。f[i][j] 的定义是，当我们拥有 j 个 i 级物品时，能达成的最大成功率。在这个时刻，我们还拥有初始的 a[i+1] 个 i+1 级物品。所以，这正好对应了子问题 g[j][a[i+1]]！

所以，f[i][j] = g[j][a[i+1]]。

整体流程

初始化:
- 确定一个物品数量的上限 MAX_ITEMS。因为目标是 n，所以 1500 左右的上限是比较安全的。
- 计算 f[m]。这是我们的初始状态函数。如果手头有 j 个 m 级物品，f[m][j] = 1.0 如果 j >= n，否则为 0.0。
逆向递推:
- 从 i = m-1 循环到 1。
- 在每个循环 i 中，我们根据 f[i+1] 来计算 f[i]。
- 具体方法是： a. 建立临时的 g[j][k] DP表。 b. j 从 0 循环到 MAX_ITEMS，k 从 MAX_ITEMS 倒序循环到 0（因为 g 的计算依赖于更大的 k 值）。 c. 根据上面推导的公式，计算出整个 g 表。 d. 计算 f[i][j] = g[j][a[i+1]] for all j.
最终答案:
- 经过所有循环，我们最终会得到 f[1] 的所有值。
- 我们一开始有 a[1] 个 1 级物品，所以答案就是 f[1][a[1]]。

空间优化

注意到 f[i] 的计算只依赖于 f[i+1]，我们可以使用滚动数组来优化空间。我们只需要 f_curr 和 f_prev 两个一维数组就够了，喵~ 同样，g[j][k] 的计算中，g[j] 只依赖于 g[j-2] 和 g[j-3]，所以 g 也可以用滚动数组优化，不过因为 g 是个临时表，直接开一个二维数组也问题不大，只要它的维度不是太大。

等等，g 是一个二维表，大小是 MAX_ITEMS * MAX_ITEMS，这太大了！但是我们再仔细看看 f[i][j] = g[j][a[i+1]]。这说明我们其实只需要 g 表中 k = a[i+1] 这一列的值！这启发我们重新设计 g 的递推，让它不依赖于 k 的绝对值。但更直接的方法是，认识到 g 的计算 O(MAX_ITEMS^2) 对于每一层 i 来说是必须的，虽然看起来很慢，但 C++ 凭借其优秀的性能，是可以通过的！

代码实现

这是我根据上面的思路，精心重构的一份代码，希望能帮助你理解呐~

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

// 定义物品数量的上限，n最大为1500，我们留一些余量
const int MAX_ITEMS = 1550;

// dp[i][j] 表示在第i层拥有j个物品时的最大成功概率
// 使用滚动数组优化空间，dp[0]和dp[1]交替表示 f[i] 和 f[i+1]
double dp[2][MAX_ITEMS];

// g[j][k] 是子问题的DP表，表示有j个i-1级物品和k个i级物品时的最大成功率
double g[MAX_ITEMS][MAX_ITEMS];

int main() {
    // 加速输入输出，喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    double p, q;
    cin >> n >> m >> p >> q;

    vector<int> a(m + 1);
    for (int i = 1; i <= m; ++i) {
        cin >> a[i];
    }

    // 1. 初始化最高等级 m 的情况 (Base Case)
    // f[m][j] = (j >= n) ? 1.0 : 0.0
    int m_idx = m % 2;
    for (int j = 0; j < MAX_ITEMS; ++j) {
        if (j >= n) {
            dp[m_idx][j] = 1.0;
        } else {
            dp[m_idx][j] = 0.0;
        }
    }

    // 2. 从 m-1 级逆向递推到 1 级
    for (int i = m - 1; i >= 1; --i) {
        int curr_level_idx = i % 2;
        int next_level_idx = (i + 1) % 2;

        // 计算子问题 g 表
        // g[j][k] 表示有 j 个 i 级物品和 k 个 i+1 级物品时的成功率
        
        // Base case for g: j < 3, 无法合成
        for (int k = 0; k < MAX_ITEMS; ++k) {
            g[0][k] = dp[next_level_idx][k];
            g[1][k] = dp[next_level_idx][k];
            g[2][k] = dp[next_level_idx][k];
        }

        // Recursive step for g: j >= 3
        // j 是 i 级物品数量，k 是 i+1 级物品数量
        for (int j = 3; j < MAX_ITEMS; ++j) {
            // k 需要从大到小遍历，因为 g[j][k] 依赖于 g[...][k+1] 和 g[...][k+2]
            for (int k = MAX_ITEMS - 3; k >= 0; --k) {
                // 稳健配方
                double prob1 = p * g[j - 2][k + 1] + (1.0 - p) * g[j - 3][k + 1];
                // 激进配方
                double prob2 = q * g[j - 3][k + 2] + (1.0 - q) * g[j - 3][k + 1];
                g[j][k] = max(prob1, prob2);
            }
        }

        // 更新 f[i] 的值
        // f[i][j] = g[j][a[i+1]]
        for (int j = 0; j < MAX_ITEMS; ++j) {
            if (a[i+1] < MAX_ITEMS) {
                dp[curr_level_idx][j] = g[j][a[i+1]];
            } else {
                // 如果初始 i+1 级物品就很多，成功率肯定是1
                dp[curr_level_idx][j] = 1.0; 
            }
        }
    }
    
    // 3. 最终答案
    // 我们初始有 a[1] 个 1 级物品
    int final_idx = 1 % 2;
    double final_ans = 0.0;
    if (a[1] < MAX_ITEMS) {
        final_ans = dp[final_idx][a[1]];
    } else {
        // 如果初始 1 级物品就爆表了，那肯定能成功
        final_ans = 1.0;
    }

    cout << fixed << setprecision(8) << final_ans << endl;

    return 0;
}

复杂度分析

时间复杂度: $O(m \cdot N^2)$ , 其中 $N$ 是我们设置的物品数量上限 MAX_ITEMS。外层循环 m 次，每次都需要计算一个 $N \times N$ 的 g 表。虽然看起来很大，但因为 m 很小（最大为8），并且C++跑得快，所以是可以通过的，喵~
空间复杂度: $O(N^2)$ 。主要是 g 表占用的空间。dp 数组因为用了滚动数组，空间是 $O(N)$ 。如果 g 表也用滚动数组优化（对 j 维度），空间可以降到 $O(N \cdot N_{const})$ ，但实现会更复杂一些，目前的 $O(N^2)$ 已经足够了。

知识点总结

概率动态规划 (Probability DP): 解决与概率和期望相关的最优化问题的有力工具。通常状态定义会包含“在某种情况下，达成目标的概率/期望是多少”。
逆向DP (Backward DP): 当正向递推关系不明确，而从目标状态反推初始状态关系更清晰时，逆向DP是绝佳的选择。本题就是从最终目标（m级物品）倒推每级物品的“价值”（成功概率）。
DP中的子问题建模: 复杂DP问题常常可以分解。本题中，从 f[i+1] 到 f[i] 的转移本身就是一个独立的、可以用DP解决的子问题（g表的计算），这是一种“DP套DP”的模式。
滚动数组优化: 在DP中，如果当前状态只依赖于前一个或前几个状态，可以用滚动数组将空间复杂度降低一个维度。这里 f[i] 只依赖 f[i+1]，是滚动数组的经典应用场景。

希望这篇题解能帮到你！解题就像炼金，需要耐心、智慧和一点点灵感，祝你在算法的世界里收获满满，喵~！

莫娜与阿贝多 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

核心思想：定义“状态函数” ​

状态转移：从 f[i+1] 到 f[i] ​

子问题的DP：g[j][k] ​

连接 g 和 f ​

整体流程 ​

空间优化 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​