[CERC2014] Outer space invaders

题目链接

题意

　　你受到一群外星人的攻击，第 $i$ 个外星人会在 $ai$ 时间出现，与你的距离为 $di$，且必须在 $bi$ 时间前消灭。你有一个区域冲击波器，每次攻击可以设定一个功率 $R$，这次攻击内会消灭所有距离 $R$ 内的所有外星人，并消耗 $R$ 单位的燃料电池。求消灭所有外星人所需的最少单位的燃料电池。

分析

　　由于我们可以先求出小区间内的最小花费，再合并成大区间，这是一个区间DP

　　设 $f[i][j]$ 表示消灭时间范围为区间 $[i,j]$ 内所有敌人（出现时间和消灭时间均在区间内），如果区间内不存在敌人，那么该值为 $0$

　　那么问题就来了，我们应该怎样枚举区间内的断点

　　我们需要先找出区间内距离最远的敌人，这样就能保证得到的花费是最优的，然后我们要将两个不包含该敌人的区间合并，所以断点应该从该敌人的出现时间枚举到消灭时间

　　于是可以得到状态转移方程（ $x$ 为区间内距离最远的敌人） $$f[i][j]=min(f[i][j],f[i][k]+d[x]+f[k+1][j])$$

　　还有因为时间的范围比较大，开二维数组会MLE，所以要把时间点离散化

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 305

int T, n;
int a[N], b[N], d[N], f[2 * N][2 * N];
int q[2 * N], qn;

int main() {
    scanf("%d", &T);
    while (T--) {
        qn = 0;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d%d%d", a + i, b + i, d + i);
            q[++qn] = a[i]; q[++qn] = b[i];
        }
        sort(q + 1, q + qn + 1);
        qn = unique(q + 1, q + qn + 1) - q - 1;
        for (int i = 1; i <= n; i++) {
            a[i] = lower_bound(q + 1, q + qn + 1, a[i]) - q;
            b[i] = lower_bound(q + 1, q + qn + 1, b[i]) - q;
        }
        memset(f, 0x3f, sizeof f);
        for (int l = 1; l <= qn; l++)
            for (int i = 1; i + l - 1 <= qn; i++) {
                int j = i + l - 1, x = 0;
                for (int k = 1; k <= n; k++)
                    if (i <= a[k] && b[k] <= j && d[k] > d[x]) x = k;
                if (!x) {f[i][j] = 0; continue;}
                for (int k = a[x]; k <= b[x]; k++)
                    f[i][j] = min(f[i][j], f[i][k - 1] + d[x] + f[k + 1][j]);
            }
        printf("%d
", f[1][qn]);
    }

    return 0;
}