poj3171 Cleaning Shifts[DP]

https://vjudge.net/problem/POJ-3171。(有价值的区间全覆盖问题)


(lyd例题)朴素DP很好想,$f[i]$表示将右端点从小到大排序后从$L$(要求覆盖的大区间)到第$i$个区间的右端点都覆盖完成时最小化费。无解则为INF。然后利用排序、右端点单调性,每次枚举前面dp过的右端点落在现在左端点及其右侧(或相邻)的,去最小dp值加上现在费用。然后$O(n^2)$就可以水过啦。。因为常数特别小,数据也才1e4嘛。。优化的话因为每次查的都是一段区间里的右端点最值,所以线段树维护即可。


细节提示:

  • 注意:好像没什么注意的。。线段树因为正常写的话值域与他下标无关的,所以这题查询区间有-1什么的也无妨,在线段树中只是体现出区间不断减半,下标增多。
  • RE:空间。。。、
  • 如果区间范围较大考虑离散化,将每个区间的L-1以及R离散化即可
 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define dbg(x) cerr<<#x<<" = "<<x<<endl
#define ddbg(x,y) cerr<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl
using namespace std;
typedef long long ll;
template<typename T>inline char MIN(T&A,T B){return A>B?A=B,:;}
template<typename T>inline char MAX(T&A,T B){return A<B?A=B,:;}
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline T read(T&x){
x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;
while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;
}
const int N=+,M=+,INF=0x3f3f3f3f;
struct kugen{
int l,r,w;
}A[N];
inline bool cmp(kugen a,kugen b){return a.r<b.r;}
int f[N],minv[M<<];
#define lc i<<1
#define rc i<<1|1
int Query(int i,int L,int R,int ql,int qr){
if(ql<=L&&qr>=R)return minv[i];
int mid=L+R>>,ret=INF;
if(ql<=mid)MIN(ret,Query(lc,L,mid,ql,qr));
if(qr>mid)MIN(ret,Query(rc,mid+,R,ql,qr));
return ret;
}
void Modify(int i,int L,int R,int x){
if(L==R)MIN(minv[i],f[x]);
else{
int mid=L+R>>;
A[x].r<=mid?Modify(lc,L,mid,x):Modify(rc,mid+,R,x);
minv[i]=_min(minv[lc],minv[rc]);
}
}
#undef lc
#undef rc
int n,m,L,R,l,r,x,ans,rb; int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);
read(m),read(L),read(R);
for(register int i=;i<=m;++i){
read(l),read(r),read(x);
if(r<L||l>R)continue;
A[++n].l=_max(l,L),A[n].r=_min(R,r),A[n].w=x;
MAX(rb,A[n].r);
}
sort(A+,A+n+,cmp);ans=INF;
memset(minv,0x3f,sizeof minv);
for(register int i=;i<=n;++i){
if(A[i].l==L)f[i]=A[i].w;else f[i]=INF;
MIN(f[i],Query(,-,rb,A[i].l-,A[i].r-)+A[i].w);
Modify(,-,rb,i);
if(A[i].r==R&&(f[i]^INF))MIN(ans,f[i]);
}
printf("%d\n",ans^INF?ans:-);
return ;
}
上一篇:RR和RC复合语句加锁


下一篇:poj2376 Cleaning Shifts【线段树】【DP】