题目描述
https://codeforces.com/gym/103049/problem/G
简要题意：现在有一个迷宫，迷宫是一个长度为 $n$ 的数轴，共有 $m$ 个 $boss$，第 $i$ 个 $boss$ 的位置为 $t_i$，秒杀成功的概率为 $p_i$，秒杀失败则需要花 $d_i$ 的时间，你的速度为 $1$，现在这个迷宫的通关记录为 $r$，求如果你想破纪录期望最少需要花费多少时间，你可以在任何时候重来
$n < r\le 5000,m\le 50$
Solution
显然我们只会在秒杀某个 $boss$ 失败后才会重来，我们令 $f[i][j]$ 表示已经秒杀第 $i$ 个 $boss$，且走到第 $i+1$ 个 $boss$ 前还没有挑战，期望最少花费多少时间破纪录
显然我们有 $f[n][k]=n-t_m$，其中 $k\in[0,r-m)$，那么对于 $f[i][j]$ 的转移，我们可以得到其值为
1
2
| f[i][j] = p[i] * (t[i + 1] - t[i] + f[i + 1][j]) +
(1 - p[i]) * min(j + d[i] >= k - m ? INF : d[i] + t[i + 1] - t[i] + f[i + 1][j + d[i]], f[0][0]);
|
我们注意到转移中出现 $f[0][0]$，且有一个 $min$，我们不能直接设 $f[0][0]$ 的值为 $x$，但我们可以二分 $f[0][0]$ 的值，如果最后算出来的 $f[0][0]$ 比我们二分的值大，则说明我们二分值太小，否则太大，按照这个结果二分即可
时间复杂度 $O(nm\log )$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#define maxn 52
#define maxm 5010
#define INF 100000000000000000
#define ll long long
using namespace std;
const long double eps = 1e-9;
int n, m, k, t[maxn], d[maxn];
double p[maxn];
double f[maxn][maxm];
bool check(double x) {
for (int i = 0; i < k - m; ++i) f[n + 1][i] = 0;
for (int i = n; ~i; --i)
for (int j = 0; j < k - m; ++j) {
f[i][j] = p[i] * (t[i + 1] - t[i] + f[i + 1][j]) +
(1 - p[i]) * min(j + d[i] >= k - m ? INF :
d[i] + t[i + 1] - t[i] + f[i + 1][j + d[i]], x);
}
return f[0][0] <= x;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> m >> k >> n;
for (int i = 1; i <= n; ++i) cin >> t[i] >> p[i] >> d[i];
p[0] = 1; t[n + 1] = m;
double l = 0, r = 1e9, mid, ans;
for (int i = 0; i < 100; ++i) {
mid = (l + r) / 2;
if (check(mid)) ans = mid, r = mid;
else l = mid;
} cout << fixed << setprecision(7) << ans << "\n";
return 0;
}
|