Luogu P4766 [CERC2014]Outer space invaders

题目描述

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;
}