题目

来自外太空的外星人（最终）入侵了地球。保卫自己，或者解体，被他们同化，或者成为食物。迄今为止，我们无法确定。

外星人遵循已知的攻击模式。有 $N$ 个外星人进攻，第 $i$ 个进攻的外星人会在时间 $a_i$ 出现，距离你的距离为 $d_i$，它必须在时间 $b_i$ 前被消灭，否则被消灭的会是你。

你的武器是一个区域冲击波器，可以设置任何给定的功率。如果被设置了功率 $R$，它会瞬间摧毁与你的距离在 $R$ 以内的所有外星人（可以等于），同时它也会消耗 $R$ 单位的燃料电池。

求摧毁所有外星人的最低成本（消耗多少燃料电池），同时保证自己的生命安全。

题解

区间dp套路题 + 1

设f[i][j]为消灭开始和消灭时间都在[i, j]的alien消耗的最小值

转移，找到这里面的 距离最远的 alien ，枚举它是在哪一时刻被消灭的

然后就会被划分成两部分，f[i][时间-1]和f[时间+1][j]

锅

离散化的b数组和输入的b数组混了（

代码

#include<bits/stdc++.h>

using namespace std;
const int N = 310;
int T, n;
int a[N], b[N], d[N];

const int M = 610;
int lib[M], btop, lic[M], ctop; 

int f[M][M];

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);

	cin >> T;

	while (T -- )
	{
		cin >> n;
		btop = ctop = 0;
		for(int i = 1;i <= n;i++)
		{
			cin >> a[i] >> b[i] >> d[i];
			lib[++ btop] = a[i], lib[++ btop] = b[i];
		}
		sort(lib + 1, lib + 1 + btop);
	
		for(int i = 1;i <= btop;i++)
		{
			if(lib[i] != lib[i - 1])
			{
				lic[++ ctop] = lib[i];
			}
		}
	
		for(int i = 1;i <= n;i++)
		{
			a[i] = lower_bound(lic + 1, lic + 1 + ctop, a[i]) - lic;
			b[i] = lower_bound(lic + 1, lic + 1 + ctop, b[i]) - lic;
//			cout << a[i] << " " << b[i] << endl;
		}//a, b此时都在0到ctop范围内 
		memset(f, 0x3f, sizeof f);
	
		for(int len = 1;len <= ctop;len++)
		{
			for(int i = 1;i + len - 1 <= ctop;i++)
			{
				int j = i + len - 1;
				int maxid = 0;
				for(int k = 1;k <= n;k++)
				{
					if(i <= a[k] && b[k] <= j)
					{
						if(d[maxid] < d[k])
						{
							maxid = k;
						}
					}
				}
				if(maxid == 0)
				{
					f[i][j] = 0;
					continue;
				}
				for(int k = a[maxid];k <= b[maxid]/**/;k++)
				{
					f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 1][j] + d[maxid]);
				}
			}
		}
		printf("%d\n", f[1][ctop]);
	}



	return 0;
}