题目描述
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; }
|