优美的闪电

一开始的思路是：当前剩余权值最大的那个区间一定要被一发能
量为该区间权值的导弹打掉，所以我们枚举该导弹击打位置，同
时我们删除所有能被该导弹击打掉的区间，但是这只针对样例,对于题目的其他数据就是不成立的。

正确的是使用区间 dp, fi,j 表示坐标被 [i, j] 完全包含 的区间最小需要花费的能量。则可以用暴力时候的思想，最大权值的区间需要一发单独的，且能量为该权值的导弹去消除。则枚举该导弹发射的坐标 x, 则子问题变成了 fi,x−1, fx+1,j。因为跨过 x 的区间一定都会被打掉，因为我们使用的是最大权值的能量。剩余的区间被 [i, x − 1], [x + 1, j] 完全包含。转移方程fi,j=minaMaxi,j≤x≤bmaxi,j{fi,x−1 + fx+1,j + wMaxi,j}时间复杂度 O(n3)。不过需要一点预处理： 离散化坐标。预处理出被 [i, j] 完全包含的最大权值的区间，即 Maxi,j。

#include<bits/stdc++.h>
using namespace std;
const int N=310,M=N*2;
struct Ed
{
 int l,r,v;
}a[N];
int b[M],n,m;
int dp[M][M];
int main()
{
 cin>>n;
 for(int i=1;i<=n;i++)
  cin>>a[i].l>>a[i].r>>a[i].v,b[++m]=a[i].l,b[++m]=a[i].r;
 sort(b+1,b+m+1);
 m=unique(b+1,b+2*n+1)-b-1;
 for(int i=1;i<=n;i++)
 {
  a[i].l=lower_bound(b+1,b+m+1,a[i].l)-b;
  a[i].r=lower_bound(b+1,b+m+1,a[i].r)-b;
 }
 for(int i=1;i<=m;i++)
 {
  for(int j=1;j+i-1<=m;j++)
  {
   int l=j+i-1;
   Ed tmp=(Ed){0,0,0};
   for(int k=1;k<=n;k++)
   {
    if(a[k].l>=j&&a[k].r<=l&&a[k].v>tmp.v)
     tmp=a[k];
   }
   if(!tmp.l)
   {
    dp[j][l]=0;
    continue;
   }
   dp[j][l]=1000000000;
   for(int k=tmp.l;k<=tmp.r;k++)
   {
    dp[j][l]=min(dp[j][l],dp[j][k-1]+dp[k+1][l]+tmp.v);
   } 
  }
 }
 cout<<dp[1][m]<<endl;
 return 0;
}