【POJ3171】Cleaning Shifts 带权区间最小覆盖

题目大意：给定一个长度为 N 的序列，求带权区间最小覆盖。

题解：设 \(dp[i]\) 表示从左端点到 i 的最小权值是多少，则状态转移为：\(dp[e[i].ed]=min\{dp[j]，j\in[e[i].st-1,e[i].ed-1] \}\)，初始化 \(dp[st-1]=0\) 即可。因此，这里用线段树来维护区间最小值即可。不过这道题需要注意的点有很多，首先开始区间的下标从 0 开始，因此需要注意避免下标为负数的情况，我采用了所有坐标加 1 的写法，结尾要注意所给区间排序之后末尾可能出现大于给定的结尾的情况，线段树需要维护两者较大的值。其次是状态转移时，线段树中的 modify 函数并不是直接修改值，而是需要比较一下大小再决定是否修改。（在这里WA了好长时间QAQ）

代码如下

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <iostream>

using namespace std;

const int maxn=1e5;

const int inf=0x3f3f3f3f;

inline int read(){

	int x=0,f=1;char ch;

	do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));

	do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));

	return f*x;

}

struct node{

	#define ls t[k].lc

	#define rs t[k].rc

	int lc,rc,mi;

}t[maxn<<1];

int tot=1;

int n,st,ed,ans,dp[maxn],l_b,r_b;

struct seg{

	int st,ed,w;

	bool operator<(const seg& y)const{return this->ed<y.ed;}

}e[10010];

inline void pushup(int k){t[k].mi=min(t[ls].mi,t[rs].mi);}

void build(int k,int l,int r){

	if(l==r){t[k].mi=dp[l];return;}

	int mid=l+r>>1;

	ls=++tot,build(ls,l,mid);

	rs=++tot,build(rs,mid+1,r);

	pushup(k);

}

void modify(int k,int l,int r,int pos,int val){

	if(l==r){t[k].mi=min(t[k].mi,val);return;}

	int mid=l+r>>1;

	if(pos<=mid)modify(ls,l,mid,pos,val);

	else modify(rs,mid+1,r,pos,val);

	pushup(k);

}

int query(int k,int l,int r,int x,int y){

	if(l==x&&r==y)return t[k].mi;

	int mid=l+r>>1;

	if(y<=mid)return query(ls,l,mid,x,y);

	else if(x>mid)return query(rs,mid+1,r,x,y);

	else return min(query(ls,l,mid,x,mid),query(rs,mid+1,r,mid+1,y));

}

void read_and_parse(){

	memset(dp,0x3f,sizeof(dp));

	n=read(),st=read()+1,ed=read()+1;//偏移量

	for(int i=1;i<=n;i++){

		scanf("%d%d%d",&e[i].st,&e[i].ed,&e[i].w);

		++e[i].st,++e[i].ed;

	}

	sort(e+1,e+n+1);

	r_b=max(ed,e[n].ed),l_b=st-1;

	dp[st-1]=0;

	build(1,l_b,r_b);

}

void solve(){

	for(int i=1;i<=n;i++){

		int mi=query(1,l_b,r_b,e[i].st-1,e[i].ed-1);

		if(mi==inf)continue;

		dp[e[i].ed]=mi+e[i].w;

		modify(1,l_b,r_b,e[i].ed,dp[e[i].ed]);

	}

	ans=inf;

	for(int i=ed;i<=r_b;i++)ans=min(ans,dp[i]);

	if(ans==inf)puts("-1");

	else printf("%d\n",ans);

}

int main(){

	read_and_parse();

	solve();

	return 0;

}

巴特西

【POJ3171】Cleaning Shifts 带权区间最小覆盖

最新文章

热门文章