传送门
区间dpdpdp好题。
首先肯定需要把坐标离散化。
然后在数轴上面区间dpdpdp.
对于当前区间，区间中最大的数一定会被选。
于是我们记f[i,j]f[i,j]f[i,j]表示所有左端点在iii以及其后面，右端点在jjj以及其前面的所有外星人gggggg的最小花费。
由于最大的一定被选。
于是我们枚举它是在哪个时间点被选的。
然后用f[i][k−1],f[k+1][j]f[i][k-1],f[k+1][j]f[i][k−1],f[k+1][j]转移过来就行了。（时间点经过了kkk的都不会再被选了）
代码：
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=305;
int T,n,val[N<<1],siz=0,f[N<<1][N<<1];
struct Node{int s,t,r;}p[N],mx[N<<1][N<<1];
inline int dfs(int l,int r){
if(~f[l][r])return f[l][r];
if(r<l||!mx[l][r].r)return f[l][r]=0;
Node mxn=mx[l][r];
f[l][r]=0x3f3f3f3f;
for(int k=mxn.s;k<=mxn.t;++k)f[l][r]=min(f[l][r],dfs(l,k-1)+dfs(k+1,r)+mxn.r);
return f[l][r];
}
int main(){
T=read();
while(T--){
n=read(),memset(f,-1,sizeof(f)),memset(mx,0,sizeof(mx)),siz=0;
for(int i=1;i<=n;++i)val[++siz]=p[i].s=read(),val[++siz]=p[i].t=read(),p[i].r=read();
sort(val+1,val+siz+1),siz=unique(val+1,val+siz+1)-val-1;
for(int i=1;i<=n;++i)p[i].s=lower_bound(val+1,val+siz+1,p[i].s)-val,p[i].t=lower_bound(val+1,val+siz+1,p[i].t)-val;
for(int i=1;i<=n;++i)for(int l=p[i].s;l;--l)for(int r=p[i].t;r<=siz;++r)if(mx[l][r].r<p[i].r)mx[l][r]=p[i];
printf("%d\n",dfs(1,siz));
}
return 0;
}