POJ 3171(区间覆盖最小代价）

Posted on by
内容目录
Language:
Cleaning Shifts
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 2093   Accepted: 735

Description

有N (1 <= N <= 10,000)个区间，求覆盖[M,E](0 <= M <= E <= 86,399)的最小代价.
每个区间的代价为S (where 0 <= S <= 500,000).

Input

第一行3个整数: N, M, E. 

第二行到第n+1行，每行3个数，分别表示第i-1个区间的左端点T1,右端点T2,和代价S.

Output

仅一行表示最小代价，无解输-1.

Sample Input

3 0 4
0 2 3
3 4 2
0 0 1

Sample Output

5

Hint

样例解释
取第一个和第二个区间。

Source

USACO 2005 December Silver

这题是一个Dp问题，先列出Dp方程。
F[i]表示取[M,i]这个区间的代价
显然F[M-1]=0,答案就是F[E]
则方程为F[a[i].T2]=min(F[j])+a[i].S (T1-1<=J<=T2-1)
a[i]按T2从小到大排列；
那么显然a[i]取时，[M,T1-1]已经被前面的给取了，
因为如果被后面的[t1,t2] 取了,那么必有t1<T1 T2<t2， 就没必要取[T1,T2]了。

取最小的数可以用线段树做O(NlogN)。


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (10000+10)
#define MAXE (86399)
#define MAXS (500000+10)
#define INF (9187201950435737471)
int n,s,e;
struct SegMent
{
	int l,r;
	long long S;
	SegMent(){}
	SegMent(int _l,int _r,long long _S):l(_l),r(_r),S(_S){}
	friend bool operator<(const SegMent a,const SegMent b){return a.r<b.r;}
}a[MAXN];
struct SegMentTree //min()
{
	int n,M;
	long long t[MAXE*10];
	void fillchar(int _n)
	{
		n=_n+2;
		M=1;while (M-2<n) M<<=1;
		memset(t,127,sizeof(t));
	}
	void update(int x)
	{
		for (x>>=1;x;x>>=1) t[x]=min(t[x<<1],t[(x<<1)^1]);
	}
	void insert(int x,long long c)
	{
		x=x+2;
		x+=M;
		if (t[x]>c) {t[x]=c; update(x);	}
	}
	long long find(int l,int r)
	{
		l=l+2;r=r+2;

		l=l-1+M;r=r+1+M;
		long long ans=INF;
		while (l^r^1)
		{
			if (~l&1) ans=min(ans,t[l+1]);
			if (r&1) ans=min(ans,t[r-1]);
			l>>=1;r>>=1;
		}
		return ans;
	}
}t;
int main()
{
//	freopen("poj3171.in","r",stdin);
	scanf("%d%d%d",&n,&s,&e);
	for (int i=1;i<=n;i++) scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].S);
	sort(a+1,a+1+n);
	t.fillchar(e);
	t.insert(s-1,0);
	for (int i=1;i<=n;i++)
	{
		if (a[i].r<s) continue;
		t.insert(a[i].r,t.find(max(s-1,a[i].l-1),a[i].r-1)+a[i].S);
	}
/*	for (int i=t.M;i<=t.M*2;i++) cout<<t.t[i]<<' ';
	cout<<endl;
*/	if (t.t[e+2+t.M]==INF) cout<<"-1n";
	else cout<<t.t[e+2+t.M]<<endl;


	return 0;
}