题目#

来自外太空的外星人（最终）入侵了地球。保卫自己，或者解体，被他们同化，或者成为食物。迄今为止，我们无法确定。

外星人遵循已知的攻击模式。有 $N$ 个外星人进攻，第 $i$ 个进攻的外星人会在时间 $a_i$ 出现，距离你的距离为 $d_i$ ，它必须在时间 $b_i$ 前被消灭，否则被消灭的会是你。

你的武器是一个区域冲击波器，可以设置任何给定的功率。如果被设置了功率 $R$ ，它会瞬间摧毁与你的距离在 $R$ 以内的所有外星人（可以等于），同时它也会消耗 $R$ 单位的燃料电池。

求摧毁所有外星人的最低成本（消耗多少燃料电池），同时保证自己的生命安全。

题解#

区间dp套路题 + 1

设f[i][j]为消灭开始和消灭时间都在[i, j]的alien消耗的最小值

转移，找到这里面的距离最远的 alien ，枚举它是在哪一时刻被消灭的

然后就会被划分成两部分，f[i][时间-1]和f[时间+1][j]

锅#

离散化的b数组和输入的b数组混了（

代码#

1
#include<bits/stdc++.h>
2

3
using namespace std;
4
const int N = 310;
5
int T, n;
6
int a[N], b[N], d[N];
7

8
const int M = 610;
9
int lib[M], btop, lic[M], ctop;
10

11
int f[M][M];
12

13
int main()
14
{
15
  ios::sync_with_stdio(0), cin.tie(0);
16

17
  cin >> T;
18

19
  while (T -- )
20
  {
21
    cin >> n;
22
    btop = ctop = 0;
23
    for(int i = 1;i <= n;i++)
24
    {
25
      cin >> a[i] >> b[i] >> d[i];
26
      lib[++ btop] = a[i], lib[++ btop] = b[i];
27
    }
28
    sort(lib + 1, lib + 1 + btop);
29

30
    for(int i = 1;i <= btop;i++)
31
    {
32
      if(lib[i] != lib[i - 1])
33
      {
34
        lic[++ ctop] = lib[i];
35
      }
36
    }
37

38
    for(int i = 1;i <= n;i++)
39
    {
40
      a[i] = lower_bound(lic + 1, lic + 1 + ctop, a[i]) - lic;
41
      b[i] = lower_bound(lic + 1, lic + 1 + ctop, b[i]) - lic;
42
//      cout << a[i] << " " << b[i] << endl;
43
    }//a, b此时都在0到ctop范围内
44
    memset(f, 0x3f, sizeof f);
45

46
    for(int len = 1;len <= ctop;len++)
47
    {
48
      for(int i = 1;i + len - 1 <= ctop;i++)
49
      {
50
        int j = i + len - 1;
51
        int maxid = 0;
52
        for(int k = 1;k <= n;k++)
53
        {
54
          if(i <= a[k] && b[k] <= j)
55
          {
56
            if(d[maxid] < d[k])
57
            {
58
              maxid = k;
59
            }
60
          }
61
        }
62
        if(maxid == 0)
63
        {
64
          f[i][j] = 0;
65
          continue;
66
        }
67
        for(int k = a[maxid];k <= b[maxid]/**/;k++)
68
        {
69
          f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 1][j] + d[maxid]);
70
        }
71
      }
72
    }
73
    printf("%d\n", f[1][ctop]);
74
  }
75

76

77

78
  return 0;
79
}