题目描述
https://www.luogu.com.cn/problem/P4766
简要题意：有 $n$ 个怪兽，第 $i$ 怪兽会在 $a_i$ 时间出现，$b_i$ 时间后消失，距离为 $d_i$，现在你每个时刻都可以开枪，如果每次开枪如果范围为 $r$，则能杀掉所有与你距离小于等于 $r$ 的怪兽，但是开枪范围为 $r$ 需要花费 $r$，求杀死所有怪兽的最小话费
$n\le 300$
Solution
首先将时间离散化，我们考虑在时间上做区间 $dp$，我们考虑遵循这样的一个准则，选在若干个时间点开枪，按照某个顺序（不一定是时间顺序），如果在时间 $t$ 开枪，那么一定选择杀死所有在这个时间还活着的怪兽
那么我们定义 $f[i][j]$ 表示将出现时间和消失时间都在 $[i,j]$ 内的怪兽全部杀死的最小花费，我们枚举开枪时间 $k$，令 $g[k][i][j]$ 表示在时间 $k$ 距离最远的怪兽，那么 $f[i][j]=min(f[i][k-1]+g[k][i][j]+f[k+1][j])$
然而我们注意到，我们枚举的 $k$ 相当于是第一枪，注意到对于一个区间，距离最远的怪兽我们一定是第一个打的，所以我们的 $dp$ 转移可以简化一下，直接打区间内距离最远的那个怪兽即可
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
43
44
45
46
47
48
| #include <iostream>
#include <algorithm>
#define maxn 310
#define INF 1000000000
using namespace std;
int n, m, l[maxn], r[maxn], a[maxn];
int b[maxn * 2], cnt;
void init_hash() {
for (int i = 1; i <= n; ++i) b[i] = l[i], b[i + n] = r[i];
sort(b + 1, b + 2 * n + 1); cnt = unique(b + 1, b + 2 * n + 1) - b - 1;
for (int i = 1; i <= n; ++i) {
l[i] = lower_bound(b + 1, b + cnt + 1, l[i]) - b;
r[i] = lower_bound(b + 1, b + cnt + 1, r[i]) - b;
}
}
int f[maxn * 2][maxn * 2];
void work() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> l[i] >> r[i] >> a[i];
init_hash();
for (int i = 1; i <= cnt; ++i)
for (int j = 1; j <= cnt; ++j) f[i][j] = INF;
for (int i = 1; i <= cnt; ++i) f[i][i] = f[i][i + 1] = 0;
for (int i = 1; i <= n; ++i)
if (r[i] == l[i] + 1) f[l[i]][r[i]] += a[i];
for (int len = 3; len <= cnt; ++len)
for (int i = 1, j = len; j <= cnt; ++i, ++j) {
int p = 0; l[0] = i + 1; r[0] = j - 1;
for (int k = 1; k <= n; ++k)
if (i <= l[k] && r[k] <= j && a[k] > a[p]) p = k;
for (int k = l[p]; k <= r[p]; ++k)
f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 1][j] + a[p]);
}
cout << f[1][cnt] << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while (T--) work();
return 0;
}
|