思想 ： 1 优化：题意是覆盖点，将区间看成 (l,r)转化为( l-1,r) 覆盖区间
2 核心：dp[i] 覆盖从1到i区间的最小花费
dp[a[i].r]=min (dp[k])+a[i]s; l-1=<k<=r-1
(可我总是想着从后到前，从 前到后反而更好理解）
3 离散区间---使用线段树求区间最值 时间复杂度O(nlogn)
ps （一定忍住不看别人的代码，继续加油）
1 #include <bits/stdc++.h> 2 #define lson l,m,rt*2 3 #define rson m+1,r,rt*2+1 4 using namespace std; 5 typedef long long LL; 6 struct node { 7 LL l,r,s; 8 bool operator < (const node& t) const { 9 return r<t.r; 10 } 11 }; 12 const int N=2e5+3; 13 const int MAX=0x3f3f3f3f; 14 node a[N]; 15 LL b[N]; int cnt; 16 int tree[N*4]; 17 int n; LL M,E; 18 LL ans; 19 inline void pushup (int rt) { 20 tree[rt]=min (tree[rt*2],tree[rt*2+1]); 21 } 22 inline int mapp (LL x) { 23 return lower_bound(b+1,b+1+cnt,x)-b; 24 } 25 void update (int p,int k,int l,int r,int rt) { 26 if (l==r) { 27 tree[rt]=min (k,tree[rt]); 28 return ; 29 } 30 int m=(l+r)/2; 31 if (p<=m) update (p,k,lson); 32 else update (p,k,rson); 33 pushup(rt); 34 return ; 35 } 36 int query (int L,int R,int l,int r,int rt) { 37 if (l>=L&&r<=R) return tree[rt]; 38 if (l>R||r<L) return MAX; 39 int m=(l+r)/2; 40 return min (query(L,R,lson),query(L,R,rson)); 41 } 42 int main () 43 { 44 while (~scanf ("%d %lld %lld",&n,&M,&E)) { 45 cnt=0; 46 for (int i=1;i<=n;i++) { 47 scanf ("%lld %lld %lld",&a[i].l,&a[i].r,&a[i].s); 48 a[i].l--; 49 b[++cnt]=a[i].l; b[++cnt]=a[i].r; 50 } 51 sort (b+1,b+1+cnt); cnt=1; 52 for (int i=2;i<=2*n;i++) 53 if (b[i]!=b[cnt]) 54 b[++cnt]=b[i]; 55 56 if (b[1]!=M-1||b[cnt]!=E) ans=-1; 57 else { 58 memset (tree,0x3f,sizeof(tree)); 59 sort (a+1,a+1+n); 60 update (1,0,1,cnt,1); 61 for (int i=1;i<=n;i++) { 62 int r=mapp(a[i].r); 63 int l=mapp(a[i].l); 64 int tmp=query (l,r,1,cnt,1); 65 update (r,tmp+a[i].s,1,cnt,1); 66 } 67 ans=query (cnt,cnt,1,cnt,1); 68 if (ans==MAX) ans=-1; 69 } 70 printf("%d ",ans); 71 } 72 return 0; 73 }