BZOJ 3928 - [Cerc2014] Outer space invaders

#DP
Published on 2016-06-11

题目地址
双倍经验：BZOJ 4048

描述

有 n(n≤300)n(n\le 300) 个外星人，第 ii 个外星人会在 ai(ai≤10000)a_i(a_i\le 10000) 时间出现，离你距离 di(di≤10000)d_i(d_i\le 10000)，并且必须在 bi(bi≤10000)b_i(b_i\le 10000) 之前被消灭（可在 bib_i 时被消灭）。你有一把很 NB 的武器，攻击范围是个半径为 RR 的圆，RR 可以任意调整，不过你以 RR 的范围每攻击一次就要消耗 RR 单位能量。外星人被攻击一次就会死掉。求需要消灭所有外星人的最小消耗能量。

分析

我们把外星人看做线段，分析可知一定存在最优方案，使得开炮只需要在端点处开炮，所以可以离散化 ai,bia_i, b_i。再怎么搞呢？对于最远的外星人来说，他是必须被消灭的，所以我们枚举消灭最远的外星人的开炮位置，然后递归处理就可以了。
令 dp[i][j]dp[i][j] 为处理所有被包含在 [i,j][i, j] 内的外星人所需要的最小代价，如果离散化出 mm 个节点，则 dp[0][m−1]dp[0][m - 1] 为答案。如果 [i,j][i, j] 无完整的线段，则 dp[i][j]=0dp[i][j] = 0。
再次强调 dp[i][j]dp[i][j] 中需要打死的外星人必须满足 ax≥i,bx≤ja_x \ge i, b_x \le j。

设 x\mathrm{x} 为 [i,j][i, j] 内距离最远的外星人，则：

dp[i][j]=minax≤k≤bx(dp[i][k−1]+dp[k+1][i]+dx)dp[i][j] = \min_{a_x \le k \le b_x}(dp[i][k - 1] + dp[k + 1][i] + d_x)

显然所有包含 kk 这个时间点的线段全部被武器打死（因为我们是使用的威力最大的武器），而 dp[i][k−1],dp[k+1][i]dp[i][k - 1], dp[k + 1][i] 不会完整包含这些被武器打死的线段，所以这个转移是正确的。

代码

//  Created by Sengxian on 6/11/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3928 区间 DP
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 300 + 3, INF = 0x3f3f3f3f;
int n, a[maxn], b[maxn], d[maxn], dp[maxn * 2][maxn * 2];

vector<int> vs;
int main() {
    int caseNum = ReadInt();
    while (caseNum--) {
        n = ReadInt();
        vs.clear();
        for (int i = 0; i < n; ++i)    vs.push_back(a[i] = ReadInt()), vs.push_back(b[i] = ReadInt()), d[i] = ReadInt();
        sort(vs.begin(), vs.end());
        vs.erase(unique(vs.begin(), vs.end()), vs.end());
        for (int i = 0; i < n; ++i) {
            a[i] = lower_bound(vs.begin(), vs.end(), a[i]) - vs.begin();
            b[i] = lower_bound(vs.begin(), vs.end(), b[i]) - vs.begin();
        }
        int m = vs.size();
        for (int w = 0; w <= m; ++w)
            for (int i = 0; i + w <= m; ++i) {
                int j = i + w - 1, Max = -1, idx = - 1;
                for (int k = 0; k < n; ++k)
                    if (a[k] >= i && b[k] <= j && d[k] > Max) Max = d[idx = k];
                if (Max == -1) {dp[i][j] = 0; continue;} else dp[i][j] = INF;
                for (int k = a[idx]; k <= b[idx]; ++k)
                    dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + Max);
            }
        printf("%d\n", dp[0][m - 1]);
    }
    return 0;
}
HDOJ 4997 - Biconnected