題目#
來自外太空的外星人（最終）入侵了地球。保衛自己，或者解體，被他們同化，或者成為食物。迄今為止，我們無法確定。
外星人遵循已知的攻擊模式。有 $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;
}