自动搬运

查看原文

来自洛谷，原作者为

	Cry_For_theMoon **

搬运于2025-08-24 22:03:24，当前版本为作者最后更新于2020-10-17 20:06:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

  传送门

  不是所有"数字大但是个数少"的都能离散化的，本题我们离散化只是因为我们只关注每个事件（即一个外星人的进攻，死亡）的相对关系，比如如果有一个外星人在 $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;
}