【CERC2014】Outer space invaders

· · 题解

  传送门

  不是所有"数字大但是个数少"的都能离散化的，本题我们离散化只是因为我们只关注每个事件（即一个外星人的进攻，死亡）的相对关系，比如如果有一个外星人在 4 死亡，下一个外星人出生发生在 8，且中间没有别的事件发生，那么中间那段时间是无足轻重的，因为你肯定不会在一个没有外星人存在的时间发动武器。还有一种情况就是两个外星人的出生之间没有别的事件发生，此时如果选在这段中间时间攻击，等同于放在第一个外星人出生的时候攻击，因为攻击到的对象都是一样的。只关注相对大小，这才是离散化的核心。

  进入正题：区间DP

  离散化后 n = 600，又因为本题时限 2s（然而1s就足以水过），显然复杂度吻合一般区间DP的O(n^3)。我们设计的状态自然而然想到了 f(i,j) 表示消灭时刻 [i,j] 的所有外星人的最小花费。

  区间 DP 一定会被拆成两个子区间，不管以什么方式合并。但是如果上手就是拆成两个子区间考虑，跨越子区间的在这种情况下会被考虑两次，最关键的是，虽然被考虑，但是不一定被计算，因为如果子区间里有距离更远的，他就无意义了。这样的话，我们也无法很好地消去跨越两个子区间的外星人们的影响，因为你得维护诸如哪些外星人跨越了断点 k，哪些跨越断点的外星人影响到了解，如何去掉这些影响。反正我是不会做QwQ。

  区间DP的另一大套路就是：当我不好"拆分-合并"的时候，先考虑最后执行的操作，再用这个最后执行的操作把区间分成两部分，可以视作"合并-拆分"。有时候甚至需要枚举断点-合并-拆分（顺便推荐一道用到这个思想的区间DP：传送门）。考虑这里能否确定最后一次操作，可以确定的是，该区间内出现的距离最大的外星人一定直接打掉，因为既然距离最大，不可能有打掉别人的同时打掉这个外星人的情况的出现，因此一定有一次进攻操作是针对这个距离最远的外星人的。

  设这个距离最远的外星人编号为 g，那么 [g.l,g.r]（当然指离散化后） 的所有时间段都可以打，枚举点 k，然后所有出现时间跨越了k，都消失了，那么最后一个问题也解决了：状态里的 i,j，考不考虑某个外星人的生活事件超出了 [i,j] 的情况。我们发现如果考虑，那么你计算 f(i,k-1) 和 f(k+1,j) 的时候，跨越子区间还有 k 的外星人明明被消灭了，但是在你这里没有体现，还会被计算。

  最后找不超过 [i,j] 的外星人的最大距离时没有像别的题解每次暴力枚举，也是用了 n^2 的 DP 预处理了以下，这个东西相信来做这道题的都会了，就放在代码里吧。当然因为最后DP的时候还是要枚举那个最大外星人的生存时间，所以复杂度其实并没有降下来，只是会快一点点QwQ。

//CERC,2014
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
const int MAXN=310,INF=1e9;
struct Node{
    int l,r,w;
    int bl,br; 
}node[MAXN];
int t,n,b[MAXN*2],tot;
int f[MAXN*2][MAXN*2],g[MAXN*2][MAXN*2];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        memset(g,0,sizeof g);
        set<int>s;
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&node[i].l,&node[i].r,&node[i].w);
            s.insert(node[i].l);s.insert(node[i].r);
        }
        set<int>::iterator it;
        tot = 0;
        for(it = s.begin();it!=s.end();it++){
            int v = *it;
            b[++tot] = v;
        }
        sort(b+1,b+1+tot);
        for(int i=1;i<=n;i++){
            node[i].bl = lower_bound(b+1,b+1+tot,node[i].l) - b;
            node[i].br = lower_bound(b+1,b+1+tot,node[i].r) - b;
        }
        for(int i=1;i<=n;i++){
            g[node[i].bl][node[i].br] = (node[g[node[i].bl][node[i].br]].w>node[i].w)?g[node[i].bl][node[i].br]:i;
        }
        for(int len=2;len<=tot;len++){
            for(int i=1;i+len-1<=tot;i++){
                int j=i+len-1;
                int tmp = (node[g[i][j-1]].w > node[g[i+1][j]].w) ? g[i][j-1]:g[i+1][j];
                g[i][j] = (node[tmp].w > node[g[i][j]].w) ? tmp : g[i][j];
            }
        }
        for(int len=1;len<=tot;len++){
            for(int i=1;i+len-1<=tot;i++){
                int j=i+len-1;
                if(g[i][j] == 0){
                    f[i][j] = 0;continue;
                }
                f[i][j] = INF;
                for(int k=node[g[i][j]].bl;k<=node[g[i][j]].br;k++){
                    f[i][j] = min(f[i][j],f[i][k-1]+f[k+1][j]+node[g[i][j]].w);
                }
            }
        }
        printf("%d\n",f[1][tot]);
    }

    return 0;
}