花火大会练习：最小期望练习时间

小鸟正在练习制作烟火，为即将到来的'花火大会'做准备。她制作一个烟火需要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] = min(dp[i-1] + n, dp[i-k] + m + n * k * (1 - (1 - p * 10^-4)^k))  (1 <= k <= i)

其中，dp[i-1] + n表示制作完i个烟火后，直接开始制作第i+1个烟火的期望练习时间；dp[i-k] + m + n * k * (1 - (1 - p * 10^-4)^k)表示制作完i个烟火后，点燃前k个烟火的期望练习时间。

解释：

dp[i-1] + n：制作完i个烟火后，直接开始制作第i+1个烟火，只需要n分钟的时间。
dp[i-k] + m + n * k * (1 - (1 - p * 10^-4)^k)：制作完i个烟火后，点燃前k个烟火，需要m分钟的时间点燃，然后还需要n * k * (1 - (1 - p * 10^-4)^k)分钟的时间来制作剩下的k个烟火。其中，(1 - (1 - p * 10^-4)^k)表示这k个烟火中至少有一个完美的烟火的概率。

初始状态为dp[0] = 0，最终答案为dp[n]。

代码实现

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const double eps = 1e-4;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m, p;
        cin >> n >> m >> p;
        double dp[n + 1];
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + n;
            for (int k = 1; k <= i; k++) {
                dp[i] = min(dp[i], dp[i - k] + m + n * k * (1 - pow(1 - p * 1e-4, k)));
            }
        }
        cout << fixed << setprecision(4) << dp[n] << endl;
    }
    return 0;
}