P4766 [CERC2014]Outer space invaders（区间dp）

本文主要是介绍P4766 [CERC2014]Outer space invaders（区间dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

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

输入输出格式输入格式：

第一行输入一个数T,表示有T组数据

每组数据的第一行为外星人的数量n（1<=n<=300)

接下来n+1行，每行有三个数ai,bi,di，表示这个外星人在时间ai出现，距离你di,在bi前时刻死亡

输出格式：

每组输出摧毁所有外星人的最低成本

Translated by @xzx_vyt

思路：
有两个显然的结论：

选择的点均可以在端点上
每个时间段内最远的外星人，必须在其时间范围内单独攻击。

对于结论1，如果当前的点不在端点上，那么你往前移往后移都不会影响其攻击到的外星人，于是将其一直移动到端点上就行了。

定义 $f [i] [j]$ 代表消灭时间范围在 $[i, j]$ 内的外星人需要的最低成本。
由结论1，我们只需要考虑端点，所以离散化就好了。
由结论2，每轮我们优先攻击时间范围内最远的外星人，剩下的部分在单独攻击。因为当前的这个最远外星人，现在不攻击，那么你划分完区间后还要在子区间攻击，子区间再攻击，结果肯定不会更优，所以只需要考虑每轮最远的外星人即可。

转移就是 $f [i] [j] = m i n (f [i] [j], f [i] [k - 1] + f [k + 1] [j] + a [i d] . d)$
但是注意，当 $k = i$ 的时候，可能会出现问题。解决办法是定义 $f [i] [i - 1]$ 为0，或者定义 $f [i] [j]$ 为消灭时间范围 $(i, j)$ 内外星人最低成本，改为开区间。

很多题解没有考虑这个地方，在n=1的时候输出的结果都是INF，明显错误了。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>using namespace std;
typedef long long ll;const int maxn = 605;
const int INF = 0x3f3f3f3f;struct Node {int a,d,b;
}a[maxn];int num[maxn],cnt,f[maxn][maxn];void init() {sort(num + 1,num + 1 + cnt);cnt = unique(num + 1,num + 1 + cnt) - (num + 1);
}int Find(int x) {return lower_bound(num + 1,num + 1 + cnt,x) - num;
}int main() {int T;scanf("%d",&T);while(T--) {int n;scanf("%d",&n);cnt = 0;memset(f,0x3f,sizeof(f));for(int i = 1;i <= n;i++) {scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].d);num[++cnt] = a[i].a;num[++cnt] = a[i].b;f[i][i - 1] = f[i + 1][i] = 0;}init();for(int i = 1;i <= n;i++) {a[i].a = Find(a[i].a);a[i].b = Find(a[i].b);}for(int len = 1;len <= cnt;len++) {for(int i = 1;i + len - 1 <= cnt;i++) {int j = i + len - 1;int id = 0;for(int k = 1;k <= n;k++) {if(a[k].b <= j && a[k].a >= i && a[id].d < a[k].d) {id = k;}}if(!id) {f[i][j] = 0;continue;}for(int k = a[id].a;k <= a[id].b;k++) {f[i][j] = min(f[i][j],f[i][k - 1] + a[id].d + f[k + 1][j]);}}}printf("%d\n",f[1][cnt]);}return 0;
}