【洛谷】P4766 [CERC2014]Outer space invaders（区间dp）

原题链接

题意

有 (n) 个敌人，第 (i) 个敌人的距离为 (d_i)，必须在 ([a_i,b_i]) 时刻内被消灭。

可以在任意时刻消耗 (r) 的代价，消灭距离为 (r) 以内的所有敌人，求消灭所有敌人的最小代价。

(1 leq n leq 300,1 leq d_i leq 10000,1leq a_i leq b_i leq 10000)。

思路

注意到时刻的范围比较大，实际用到的时刻很少，可以将端点时刻离散化一下。

如果设 (f_i) 为消灭了按照 (b_i) 排序后前 (i) 个敌人的最小代价，可以发现消灭前 (i) 个敌人时，也可以消灭 (i+1sim n) 的敌人，而这部分对于后面的转移又有影响，所以无法直接线性转移。

既然用消灭的敌人来设计状态行不通，就可以尝试按照时间来设计状态。

考虑假设 (f_{l,r}) 为消灭了所有出现时刻在 ([l,r]) 区间内的敌人（即所有满足 (l leq a_i leq b_i leq r) 的敌人）的最小代价。这样设计状态就可以有效地避免前面提到的后效性问题。

假设在这个区间内距离最远的敌人距离为 (r)，出现时刻为 ([L,R])。那么必然会在 ([L,R]) 内选择某一时刻消耗 (r) 的代价来消灭敌人，可以得到状态转移方程：

而对于断开点 (k otin [L,R])，如 (f_{l,R-1}+f_{R+1,r}) 这类的转移，实质上在 (f_{R+1,r}) 中还是会把 (r) 计算一遍，所以这类转移是重复的，也就没必要写进转移方程内了。

code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=610,INF=0x3f3f3f3f;
int num[N],f[N][N],n,tot;
struct alien{int l,r,v;}a[N];
void solve()
{
	scanf("%d",&n);tot=0;for(int i=1;i<=n;i++) scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].v),num[++tot]=a[i].l,num[++tot]=a[i].r;
	sort(num+1,num+tot+1);tot=unique(num+1,num+tot+1)-num-1;
	for(int i=1;i<=n;i++) a[i].l=lower_bound(num+1,num+tot+1,a[i].l)-num;
	for(int i=1;i<=n;i++) a[i].r=lower_bound(num+1,num+tot+1,a[i].r)-num;
	for(int len=1;len<=tot;len++)
	    for(int l=1,r=l+len-1;r<=tot;l++,r++)
	    {
	    	f[l][r]=INF;int p=0;
	    	for(int k=1;k<=n;k++) if(a[k].l>=l&&a[k].r<=r&&a[k].v>a[p].v) p=k;
	    	if(!p) {f[l][r]=0;continue;}//也就是没有敌人的出现时刻完全在这个区间内
	    	for(int k=a[p].l;k<=a[p].r;k++) f[l][r]=min(f[l][r],f[l][k-1]+f[k+1][r]+a[p].v);
		}
	printf("%d
",f[1][tot]);
}
int main()
{
	int T;scanf("%d",&T);while(T--) solve();
	return 0;
}