[CERC2014]Outer space invaders

LCIII.[CERC2014]Outer space invaders

一种错误的思路是观察到一定可以构造出一种最优状态使得每次射击都发生在外星人消失的时刻，然后就将所有外星人按照消失时刻排序并设\(f[i,j]\)表示在第\(i\)个外星人消失的时刻如果你开了一炮高为（离散化后）\(j\)的最小费用——但很快就会发现这种DP需要记录下在这之前每一个高度上次被打的时间，于是就DP不了了。

正确的DP是将所有的端点离散化后，观察到如果我们要把被完整的包含在区间\([l,r]\)内的所有外星人全部干掉，则其中最远的那个必定要对它开一炮；于是我们便找出这一个外星人，然后枚举这一炮开在哪（设为\(p\)），就可以将其分作\([l,p-1]\)与\([p+1,r]\)两截（所有经过\(p\)的外星人都被干掉了）。

于是就可以区间DP了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
int T,n,m,f[610][610],l[310],r[310],d[310];
vector<int>v;
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n),v.clear(),memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++)scanf("%d%d%d",&l[i],&r[i],&d[i]),v.push_back(l[i]),v.push_back(r[i]);
		sort(all(v)),v.resize(m=unique(all(v))-v.begin());
		for(int i=1;i<=n;i++)l[i]=lower_bound(all(v),l[i])-v.begin()+1,r[i]=lower_bound(all(v),r[i])-v.begin()+1;
		for(int i=1;i<=m;i++)for(int j=i;j;j--){
			int id=-1;
			for(int k=1;k<=n;k++)if(j<=l[k]&&r[k]<=i&&(id==-1||d[id]<d[k]))id=k;
			if(id==-1)continue;
			f[j][i]=0x3f3f3f3f;
			for(int k=l[id];k<=r[id];k++)f[j][i]=min(f[j][i],f[j][k-1]+d[id]+f[k+1][i]);
		}
		printf("%d\n",f[1][m]);		
	}
	return 0;
}