有\(n\)个人，第\(i\)个人要在\([a_i,b_i]\)时间内于\(d_i\)点处出现。你要消灭掉这些人，每个时间可以选择一个值\(R\)使得位置不超过\(R\)的人蒸发，代价为\(R\)。
问消灭所有人的最小代价。
\(n\le 300\)
离散化，DP设\(f_{i,j}\)表示处理完全在\([i,j]\)区间内的人的最小代价。转移找到\(d_i\)最高的，枚举消灭他的时间，将区间分成两个部分。
时间复杂度\(O(n^3)\)。
PS：似乎可以用四边形不等式优化？
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 310
#define INF 30000000
int n;
struct Itv{
int l,r,d;
} a[N];
bool cmpp(int *a,int *b){return *a<*b;}
void init(){
static int *p[N],q[N];
for (int i=1;i<=n;++i)
p[i]=&a[i].r;
sort(p+1,p+n+1,cmpp);
int k=0;
for (int i=1,last=-1;i<=n;++i){
if (*p[i]!=last){
last=*p[i];
q[++k]=*p[i];
}
*p[i]=k;
}
for (int i=1;i<=n;++i)
a[i].l=lower_bound(q+1,q+k+1,a[i].l)-q;
}
int f[N][N];
int main(){
freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
while (T--){
scanf("%d",&n);
for (int i=1;i<=n;++i)
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].d);
init();
for (int i=n;i>=1;--i)
for (int j=i;j<=n;++j){
int x=-1;
for (int k=1;k<=n;++k)
if (i<=a[k].l && a[k].r<=j && (x==-1 || a[k].d>a[x].d))
x=k;
if (x==-1) f[i][j]=0;
else{
f[i][j]=INF;
for (int k=a[x].l;k<=a[x].r;++k)
f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+a[x].d);
}
}
printf("%d\n",f[1][n]);
}
return 0;
}