烟火制作练习：最小期望时间算法详解

问题描述：

小鸟正在练习制作烟火，为即将到来的花火大会做准备。她制作一个烟火需要 n 分钟，由于她并不精通制作烟火，每个烟火只有 p × 10^-4 的概率是完美的。

每当她完成一个烟火后，她可以立即开始制作下一个烟火，或者花 m 分钟点燃所有已完成的烟火。如果点燃的烟火中至少有一个完美的烟火，她会很高兴并休息。否则，她将继续练习。请问在采取最佳策略的情况下，她在休息之前的最小期望练习时间是多少？

注意：

无论剩下多少个烟火，点燃它们都需要 m 分钟。

输入格式：

有多个测试用例。第一行输入一个整数 T (1 ≤ T ≤ 10^4)，表示测试用例的数量。对于每个测试用例：

第一行为三个整数 n、m 和 p (1 ≤ n, m ≤ 10^9，1 ≤ p ≤ 10^4)。

输出格式：

对于每个测试用例，输出一行一个数字，表示最小期望练习时间。

如果绝对误差或相对误差不超过 10^-4，你的答案将被认为是正确的。

算法思路：

我们可以使用动态规划来解决这个问题。令 dp[i] 表示在已经制作了 i 个烟火的情况下，小鸟在休息之前的最小期望练习时间。

我们可以通过以下公式来计算 dp[i]：

dp[i] = min(n + dp[i + 1], m + (1 - prob^i) * dp[i])

n + dp[i + 1] 代表制作一个烟火然后继续练习，期望时间为 n 分钟加上制作 i + 1 个烟火后的最小期望练习时间 dp[i + 1]。
m + (1 - prob^i) * dp[i] 代表点燃所有烟火，期望时间为 m 分钟加上所有烟火都不完美的概率 (1 - prob^i) 乘以继续练习的最小期望时间 dp[i]。

初始状态为 dp[n] = 0，因为当制作完 n 个烟火后，小鸟可以直接休息。

C++ 代码实现：


int main() {    int T;    cin >> T;

    while (T--) {        int n, m, p;        cin >> n >> m >> p;

        double prob = p * 1e-4;        double dp[n + 1];        dp[n] = 0;

        for (int i = n - 1; i >= 0; i--) {            dp[i] = min(n + dp[i + 1], m + (1 - pow(prob, i)) * dp[i]);        }

        cout << dp[0] << endl;    }

    return 0;}

**代码解释：**

* `prob` 存储每个烟火完美的概率。
* `dp` 数组存储状态，`dp[i]` 表示制作了 `i` 个烟火后的最小期望练习时间。
* 循环从 `n - 1` 到 `0`，使用公式计算每个状态的 `dp[i]`。
* 最终输出 `dp[0]`，即制作 0 个烟火时的最小期望练习时间。

**优化：**

我们可以优化算法，避免重复计算。在计算 `dp[i]` 时，我们实际上只需要用到 `dp[i + 1]`。因此，我们可以使用一个变量来存储 `dp[i + 1]` 的值，并用它来计算 `dp[i]`，从而减少空间复杂度。

**改进后的 C++ 代码：**

```c++#include <iostream>#include <cmath>using namespace std;

int main() {    int T;    cin >> T;

    while (T--) {        int n, m, p;        cin >> n >> m >> p;

        double prob = p * 1e-4;        double next_dp = 0;

        for (int i = n - 1; i >= 0; i--) {            double current_dp = min(n + next_dp, m + (1 - pow(prob, i)) * next_dp);            next_dp = current_dp;        }

        cout << next_dp << endl;    }

    return 0