题解 P4766 【[CERC2014]Outer space invaders】
ShineEternal
2020-11-24 22:25:15
[link](https://blog.csdn.net/kkkksc03/article/details/110098711)
## description：
有 $n$ 个外星人进攻，第 $i$ 个进攻的外星人会在时间 $a_i$ 出现，距离你的距离为 $d_i$ ，它必须在时间 $b_i$ 前被消灭，否则被消灭的会是你。
你的武器是一个区域冲击波器，可以设置任何给定的功率。如果被设置了功率 $R$，它会瞬间摧毁与你的距离在 $R$ 以内的所有外星人（可以等于），同时它也会消耗 $R$ 单位的燃料电池。（个人注解：这个冲击波是**瞬时**的。）
求摧毁所有外星人的最低成本（消耗多少燃料电池），同时保证自己的生命安全。
## solution：
这道题我们可以考虑区间dp。
设 $f[l][r]$ 表示在 $[l,r]$ 上最低的成本。
但是我们发现，坐标的范围达到了 $1e4$，这就意味着数组也会开得较大。我们不妨离散化一下。（因为 $n$ 较小）
然后考虑如何转移。
发现对于一段时间区间，我们可以贪心的消去最远的外星人，这样浪费就少。
于是，我们以最远的外星人为转移契机：
$f[l][r]=f[l][k-1]+f[k+1][r]+d[tag](a[tag]\leq k\leq b[tag])$，其中 $tag$ 为该段时间内最远的外星人的序号。
```cpp
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
map<int,int>mp;
int f[705][705];//f[l][r]表示[l,r]这段时间所需的花费。
int a[1005],b[1005],d[1005];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(f,0,sizeof(f));
for(int i=1;i<=10000;i++)mp.clear();
int n,cnt=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i],&b[i],&d[i]);
mp[a[i]]=1;//离散
mp[b[i]]=1;
}
for(int i=1;i<=10000;i++)
{
if(mp[i]==1)
{
mp[i]=++cnt;//重新编号
}
}
for(int i=1;i<=n;i++)
{
a[i]=mp[a[i]];//赋值编排
b[i]=mp[b[i]];
}
for(int len=1;len<cnt;len++)//众所周知，区间dp的第一层循环要先枚举区间的长度。
{
//printf("test\n");
for(int i=1;i+len<=cnt;i++)//接着是区间的起始点。
{
// printf("Test2\n");
int j=i+len;
f[i][j]=1000000000;
int tag,ans=0;
for(int k=1;k<=n;k++)
{
//printf("Test3\n");
if(a[k]>=i&&b[k]<=j&&d[k]>ans)//寻找最大的外星人。
{
ans=d[k];
tag=k;
}
}
if(ans==0)
{
f[i][j]=0;
continue;
}
for(int k=a[tag];k<=b[tag];k++)//在这个最大的外星人的安全时间内的区间都可以如此合并。
f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+ans);
}
}
printf("%d\n",f[1][cnt]);
}
return 0;
}
```