https://vjudge.net/problem/POJ-3171。（有价值的区间全覆盖问题）
（lyd例题）朴素DP很好想，$f[i]$表示将右端点从小到大排序后从$L$（要求覆盖的大区间）到第$i$个区间的右端点都覆盖完成时最小化费。无解则为INF。然后利用排序、右端点单调性，每次枚举前面dp过的右端点落在现在左端点及其右侧（或相邻）的，去最小dp值加上现在费用。然后$O(n^2)$就可以水过啦。。因为常数特别小，数据也才1e4嘛。。优化的话因为每次查的都是一段区间里的右端点最值，所以线段树维护即可。
细节提示：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #define dbg(x) cerr<<#x<<" = "<<x<<endl 8 #define ddbg(x,y) cerr<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl 9 using namespace std; 10 typedef long long ll; 11 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;} 12 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;} 13 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 14 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 15 template<typename T>inline T read(T&x){ 16 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c==‘-‘)f=1; 17 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 18 } 19 const int N=10000+7,M=100000+7,INF=0x3f3f3f3f; 20 struct kugen{ 21 int l,r,w; 22 }A[N]; 23 inline bool cmp(kugen a,kugen b){return a.r<b.r;} 24 int f[N],minv[M<<2]; 25 #define lc i<<1 26 #define rc i<<1|1 27 int Query(int i,int L,int R,int ql,int qr){ 28 if(ql<=L&&qr>=R)return minv[i]; 29 int mid=L+R>>1,ret=INF; 30 if(ql<=mid)MIN(ret,Query(lc,L,mid,ql,qr)); 31 if(qr>mid)MIN(ret,Query(rc,mid+1,R,ql,qr)); 32 return ret; 33 } 34 void Modify(int i,int L,int R,int x){ 35 if(L==R)MIN(minv[i],f[x]); 36 else{ 37 int mid=L+R>>1; 38 A[x].r<=mid?Modify(lc,L,mid,x):Modify(rc,mid+1,R,x); 39 minv[i]=_min(minv[lc],minv[rc]); 40 } 41 } 42 #undef lc 43 #undef rc 44 int n,m,L,R,l,r,x,ans,rb; 45 46 int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout); 47 read(m),read(L),read(R); 48 for(register int i=1;i<=m;++i){ 49 read(l),read(r),read(x); 50 if(r<L||l>R)continue; 51 A[++n].l=_max(l,L),A[n].r=_min(R,r),A[n].w=x; 52 MAX(rb,A[n].r); 53 } 54 sort(A+1,A+n+1,cmp);ans=INF; 55 memset(minv,0x3f,sizeof minv); 56 for(register int i=1;i<=n;++i){ 57 if(A[i].l==L)f[i]=A[i].w;else f[i]=INF; 58 MIN(f[i],Query(1,-1,rb,A[i].l-1,A[i].r-1)+A[i].w); 59 Modify(1,-1,rb,i); 60 if(A[i].r==R&&(f[i]^INF))MIN(ans,f[i]); 61 } 62 printf("%d\n",ans^INF?ans:-1); 63 return 0; 64 }
原文：https://www.cnblogs.com/saigyouji-yuyuko/p/10714860.html