テーマ#
外宇宙からのエイリアン（最終的に）が地球に侵入しました。自分を守るか、解体されるか、彼らに同化されるか、食べ物になるか。今のところ、私たちは確定できません。
エイリアンは既知の攻撃パターンに従います。$N$ 体のエイリアンが攻撃し、第 $i$ 体の攻撃のエイリアンは時間 $a_i$ に現れ、あなたとの距離は $d_i$ で、時間 $b_i$ 前に排除されなければなりません。そうでなければ、排除されるのはあなたです。
あなたの武器は、任意の指定された出力を設定できる区域衝撃波器です。出力 $R$ に設定されると、あなたとの距離が $R$ 以内のすべてのエイリアンを瞬時に破壊します（等しい場合も含む）。同時に、$R$ 単位の燃料電池を消費します。
すべてのエイリアンを破壊するための最低コスト（消費する燃料電池の量）を求め、同時に自分の命を守ります。
テーマ解決#
区間 dp のパターン問題 + 1
f[i][j]を消滅開始と消滅時間が[i, j]のエイリアンを排除するのにかかる最小値とします。
転送、ここで最も距離の遠いエイリアンを見つけ、そのエイリアンがどの時点で排除されるかを列挙します。
その後、f[i][時間-1]とf[時間+1][j]の 2 つの部分に分かれます。
問題#
離散化された 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;
}