这里写的是区间dp做法，先将时间进行离散化处理
打高敌人时可以顺便干掉较矮的敌人，故每次考虑区间最高敌人
dp[i][j]表示消灭出现时间大于x小于j这一段敌人的最小花费
则dp[i][j]=dp[i][k]+dp[k][j]+mh.其中mh是i，j段出现的最高敌人的高度，k为区间内所有最高敌人可能出现的点
看见网上其他大神都拿着stl离散化各种处理，这里贴一个没什么STL的版本
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=308; const int INF=0x7f7f7f7f; struct fuck{ int x,y,h; }f[maxn]; int n; int a[maxn<<2]; int b[maxn<<2]; int dp[maxn<<2][maxn<<2]; int scan() { int res = 0, ch, flag = 0; if((ch = getchar()) == '-') //判断正负 flag = 1; else if(ch >= '0' && ch <= '9') //得到完整的数 res = ch - '0'; while((ch = getchar()) >= '0' && ch <= '9' ) res = res * 10 + ch - '0'; return flag ? -res : res; } int lb(int x,int l,int r) { int mid; while(l<=r) { mid=(l+r)>>1; if(b[mid]<x) l=mid+1; if(b[mid]==x) return mid; if(b[mid]>x) r=mid-1; } } int main() { int i,j,t,k; scanf("%d",&t); int pp[maxn]; while(t--) { scanf("%d",&n); int idx=0,id=0; for(i=1;i<=n;i++) { f[i].x=scan();f[i].y=scan();f[i].h=scan(); a[idx++]=f[i].x;a[idx++]=f[i].y; } sort(a,a+idx); b[++id]=a[0]; for(i=1;i<idx;i++) if(a[i]!=a[i-1]) b[++id]=a[i]; for(i=1;i<=n;i++) { f[i].x=lb(f[i].x,1,id); f[i].y=lb(f[i].y,1,id); } int len=id+1; for(i=0;i<=len;i++) dp[i][i]=0; for(int d=1;d<=len;d++) for(i=0;i+d<=len;i++) { int j=i+d; int mh=-1,idh=0; for(k=1;k<=n;k++) if(f[k].x>i&&f[k].y<j) { if(f[k].h>=mh) { if(f[k].h>mh) { idh=0; pp[++idh]=k; mh=f[k].h; } else pp[++idh]=k; } } if(mh==-1) dp[i][j]=0; else { dp[i][j]=INF; while(idh>0) { int xx=pp[idh--]; for(k=f[xx].x;k<=f[xx].y;k++) if(dp[i][j]>dp[i][k]+dp[k][j]+mh) dp[i][j]=dp[i][k]+dp[k][j]+mh; } } } printf("%d ",dp[0][len]); } return 0; }