题目
来自外太空的外星人（最终）入侵了地球。保卫自己，或者解体，被他们同化，或者成为食物。迄今为止，我们无法确定。
外星人遵循已知的攻击模式。有 N 个外星人进攻，第 i 个进攻的外星人会在时间 ai 出现，距离你的距离为 di，它必须在时间 bi 前被消灭，否则被消灭的会是你。
你的武器是一个区域冲击波器，可以设置任何给定的功率。如果被设置了功率 R，它会瞬间摧毁与你的距离在 R 以内的所有外星人（可以等于），同时它也会消耗 R 单位的燃料电池。
求摧毁所有外星人的最低成本（消耗多少燃料电池），同时保证自己的生命安全。
题解
区间dp套路题 + 1
设f[i][j]为消灭开始和消灭时间都在[i, j]的alien消耗的最小值
转移，找到这里面的 距离最远的 alien ，枚举它是在哪一时刻被消灭的
然后就会被划分成两部分，f[i][时间-1]和f[时间+1][j]
锅
离散化的b数组和输入的b数组混了（
代码
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include<bits/stdc++.h>
using namespace std;
const int N = 310;
int T, n;
int a[N], b[N], d[N];
const int M = 610;
int lib[M], btop, lic[M], ctop;
int f[M][M];
int main()
{
ios::sync_with_stdio(0), cin.tie(0);
cin >> T;
while (T -- )
{
cin >> n;
btop = ctop = 0;
for(int i = 1;i <= n;i++)
{
cin >> a[i] >> b[i] >> d[i];
lib[++ btop] = a[i], lib[++ btop] = b[i];
}
sort(lib + 1, lib + 1 + btop);
for(int i = 1;i <= btop;i++)
{
if(lib[i] != lib[i - 1])
{
lic[++ ctop] = lib[i];
}
}
for(int i = 1;i <= n;i++)
{
a[i] = lower_bound(lic + 1, lic + 1 + ctop, a[i]) - lic;
b[i] = lower_bound(lic + 1, lic + 1 + ctop, b[i]) - lic;
}
memset(f, 0x3f, sizeof f);
for(int len = 1;len <= ctop;len++)
{
for(int i = 1;i + len - 1 <= ctop;i++)
{
int j = i + len - 1;
int maxid = 0;
for(int k = 1;k <= n;k++)
{
if(i <= a[k] && b[k] <= j)
{
if(d[maxid] < d[k])
{
maxid = k;
}
}
}
if(maxid == 0)
{
f[i][j] = 0;
continue;
}
for(int k = a[maxid];k <= b[maxid];k++)
{
f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 1][j] + d[maxid]);
}
}
}
printf("%d\n", f[1][ctop]);
}
return 0;
}
|