区间DP
离散化后考虑一段区间(l,r)（这里指的是出现时间的区间）
那么这段区间的R的最小值至少为这一段区间最高的线段（感觉讲的很抽象啊……最高的线段高度等于这个外星人离你的距离）
然后输出(0,tb)表示在[1,tb-1]能取到的最小代价，所以中间那个tb要++，因为我用的是开区间
#include<cstdio>
#include<algorithm>
using namespace std;
int n,table[10005],tb,f[1005][1005],T;
struct Plane{
int a,b,d;
}p[305];
int main(){
freopen("3928_4048.in","r",stdin);
freopen("3928_4048.out","w",stdout);
scanf("%d",&T);
while(T--){
tb=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d %d %d",&p[i].a,&p[i].b,&p[i].d);
table[++tb]=p[i].a;
table[++tb]=p[i].b;
}
sort(table+1,table+tb+1);
tb=unique(table+1,table+tb+1)-table-1;
for(int i=1;i<=n;i++){
p[i].a=lower_bound(table+1,table+tb+1,p[i].a)-table;
p[i].b=lower_bound(table+1,table+tb+1,p[i].b)-table;
}
tb++;
for(int len=0;len<=tb;len++){
for(int i=0;i<=tb-len;i++){
int j=i+len,H=-1;
for(int k=1;k<=n;k++){
if(i<p[k].a && p[k].b<j && (H==-1 || p[H].d<p[k].d))H=k;
}
if(H==-1)f[i][j]=0;
else {
f[i][j]=2100000000;
for(int k=p[H].a;k<=p[H].b;k++){
f[i][j]=min(f[i][j],f[i][k]+f[k][j]+p[H].d);
}
}
}
}
printf("%d\n",f[0][tb]);
}
return 0;
}
评论 (0)
