Outer space invaders

[CERC2014]Outer space invaders

标签：动态规划 区间DP

---

题目描述

题目描述 来自外太空的外星人（最终）入侵了地球。保卫自己，或者解体，被他们同化，或者成为食物。迄今为止，我们无法确定。
外星人遵循已知的攻击模式。有N个外星人进攻，第i个进攻的外星人会在时间ai出现，距离你的距离为di ,它必须在时间bi前被消灭，否则被消灭的会是你。
你的武器是一个区域冲击波器，可以设置任何给定的功率。如果被设置了功率R，它会瞬间摧毁与你的距离在R以内的所有外星人（可以等于），同时它也会消耗R单位的燃料电池。
求摧毁所有外星人的最低成本（消耗多少燃料电池），同时保证自己的生命安全。

输入输出格式

输入格式：
第一行输入一个数T,表示有T组数据
每组数据的第一行为外星人的数量n（1<=n<=300)
接下来n+1行，每行有三个数ai,bi,di，表示这个外星人在时间ai出现，距离你di,在bi前时刻死亡
输出格式
每组输出摧毁所有外星人的最低成本

样例

输入样例#1：
1
3
1 4 4
4 7 5
3 4 7

输出样例#1：
7

题解

思考这样这样一个问题：如果某些外星人的出现时间段全都包含于某一段小区间，那我们在这小区间的任意一个时间点选择这些外星人中距离我们最远的距离D开炮，那么他们可以全部被消灭。
所以我们有这样一个策略：在时间区间[l,r]中选择距离我们最远的外星人a（因为最远的我们总是需要开一炮），那么他的时间区间假设为[la,ra]（l<=la<=ra<=r）我们可以枚举在[la,ra]中任意一个时间点pi开炮，那么如果剩下的某些外星人的时间区间经过了pi，那么这些外星人一定会被消灭了。因此，我们把这个大区间又分割为了两个小区间[l,p-1]与[p+1,r];
看样子这就很符合区间DP的意味了，我们采用区间合并的方式。
设f[i][j]消灭以i,j为开区间的所有外星人的最小值
（这里需要采用开区间，因为可以避免处理一些边界问题）
那么我们枚举（i,j）中离我们最远的外星人的时间k,以k作为分割点:

for(int k = la; k <= ra; k ++)
    f[i][j] = min(f[i][j], f[i][k] + f[k][j] + dis_max);

代码

#include<bits/stdc++.h>
#define N 1010
using namespace std;

int n, t;
int num[N * 10], f[N][N];
struct node{int s, t, d;}p[N];

int main()
{
    scanf("%d", &t);
    while(t --)
    {
        scanf("%d", &n);
        int tot = 1, maxn = -1;
        memset(num, 0, sizeof(num));
        memset(f, 0x3f3f3f, sizeof(f));
        for(int i = 1; i <= n; i ++)
        {
            scanf("%d%d%d", &p[i].s, &p[i].t, &p[i].d);
            num[p[i].s] = num[p[i].t] = -1;
            maxn = max(maxn, max(p[i].s, p[i].t));
        }
        for(int i = 1; i <= maxn; i ++)
            if(num[i] == -1) num[i] = tot ++;
        for(int i = 1; i <= n; i ++)
            p[i].s = num[p[i].s], p[i].t = num[p[i].t];
        for(int len = 1; len <= tot; len ++)
            for(int i = 0; i <= tot - len; i ++)
            {
                int j = len + i;
                int mx = -1, l, r;
                for(int k = 1; k <= n; k ++)
                    if(p[k].s > i && p[k].t < j && p[k].d > mx)
                       mx = p[k].d, l = p[k].s, r = p[k].t;
                if(mx == -1) {f[i][j] = 0; continue;}
                //printf("%d %d %d %d %d", i, j, l, r, mx); system("pause");
                for(int k = l; k <= r; k ++)
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j] + mx);
            }
        printf("%d\n", f[0][tot]);
    } 
    return 0;
}