这里写的是区间dp做法，先将时间进行离散化处理

打高敌人时可以顺便干掉较矮的敌人，故每次考虑区间最高敌人

dp[i][j]表示消灭出现时间大于x小于j这一段敌人的最小花费

则dp[i][j]=dp[i][k]+dp[k][j]+mh.其中mh是i，j段出现的最高敌人的高度，k为区间内所有最高敌人可能出现的点

看见网上其他大神都拿着stl离散化各种处理，这里贴一个没什么STL的版本

#include
     
      #include
      
       #include
       
        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)            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
         
          i&&f[k].y
          
           =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\n",dp[0][len]); } return 0;}