题目大意
「Codeforces 865C」Gotta Go Fast
一个游戏有 $n$ 个关卡，每个关卡有三个参数 $F_i, S_i, P_i$，表示你有 $P_i \%$ 的概率使用 $F_i$ 个单位时间通关，有 $1 - P_i \%$ 的概率使用 $S_i$ 个单位时间通关。你的目标是在 $m$ 个单位时间内按顺序连续通过所有关卡。每打完一关以后，你可以根据当前用时来进行决策。你可以继续打关，也可以重启游戏，从第一关开始从新打。问在最优策略下，达成目标需要使用的期望时间。
数据范围：$n \le 50, m \le 5 \times 10^3, F_i < S_i \le 100, 80 \le P_i \le 99$.
思路分析
很妙的一道题。
令 $\text{dp}(i, j)$ 表示从第 $i$ 关打到第 $n$ 关，还剩下 $j$ 个单位时间时，最小的期望通关时间。那么对于每关我们可以选择打或从头开始，就有：
当然，对于 $j > m$，我们有 $\text{dp}(i, j) = \text{dp}(1, 0)$。
但是有一个问题，我们在算 $\text{dp}(i, j)$ 时还不知道 $\text{dp}(1, 0)$。考虑二分答案，先假设 $\text{dp}(1, 0) = k$，然后按照上面的方成转移，算出真正的 $\text{dp}(1, 0)$。如果 $\text{dp}(1, 0) = k$，那么真正的 $\text{dp}(1, 0) \ge k$；否则 $\text{dp}(1, 0) < k$。所以根据这个来二分答案即可。
时间复杂度 $O(nm \times \log v)$
代码实现
1 | |
2 | |
3 | using namespace std; |
4 | |
5 | typedef double db; |
6 | const int maxn = 50, maxm = 5e3 + 100; |
7 | int n, lim, f[maxn + 3], s[maxn + 3]; |
8 | db p[maxn + 3], q[maxn + 3], dp[maxn + 3][maxm + 3]; |
9 | |
10 | bool check(db x) { |
11 | for (int i = n; i; i--) { |
12 | for (int j = lim + 1; j <= lim + 100; j++) { |
13 | dp[i + 1][j] = x; |
14 | } |
15 | for (int j = 0; j <= lim; j++) { |
16 | dp[i][j] = min(x, (dp[i + 1][j + f[i]] + f[i]) * p[i] + (dp[i + 1][j + s[i]] + s[i]) * q[i]); |
17 | } |
18 | } |
19 | return dp[1][0] == x; |
20 | } |
21 | |
22 | int main() { |
23 | scanf("%d %d", &n, &lim); |
24 | for (int i = 1, x; i <= n; i++) { |
25 | scanf("%d %d %d", &f[i], &s[i], &x); |
26 | p[i] = x / 100., q[i] = (100 - x) / 100.; |
27 | } |
28 | double l = 0, r = 1e9, mid; |
29 | for (int k = 0; k < 70; k++) { |
30 | mid = (l + r) / 2; |
31 | if (check(mid)) { |
32 | l = mid; |
33 | } else { |
34 | r = mid; |
35 | } |
36 | } |
37 | printf("%.12lf\n", (l + r) / 2); |
38 | return 0; |
39 | } |