【BZOJ2034】[2009国家集训队]最大收益

Description

给出N件单位时间任务，对于第i件任务，如果要完成该任务，需要占用[Si, Ti]间的某个时刻，且完成后会有Vi的收益。求最大收益。 N≤5000，1 ≤ Si ≤ Ti ≤ 108，1 ≤ Vi ≤ 108。澄清：一个时刻只能做一件任务，做一个任务也只需要一个时刻。

Input

第一行一个整数N,表示可供选择的任务个数. 接下来的第二到第N+1行，每行三个数，其中第i+1行依次为Si,Ti,Vi

Output

输出最大收益

Sample Input

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

Sample Output

HINT

共有四个任务，其中第一个任务只能在时刻1完成，第二个任务只能在时刻2做，第三个任务只能在时刻1或时刻2做，第四个任务可以在[1,3]内任一时刻完成，四个任务的价值分别为2、2、3和1。一种完成方案是：时刻1完成第一个任务，时刻2完成第三个任务，时刻3完成第四个任务，这样得到的总收益为2+3+1=6，为最大值。

题解：先搬论文。

做一下详细解释，先贪心地做收益大的任务，判断能否在不影响前面任务的条件下做这个任务，可以用类似于匈牙利的做法判断。不过，总时间太多，但是可能用到的时间点却不多，怎么找出这些时间点呢？先将所有左端点排序，然后如果当前的左端点在前面出现过，就不断++。具体过程自己搞一搞。

然后判断的时候直接用匈牙利会TLE，这里需要一个优化。因为我们每次是从左到右尝试每个时间点的，所以如果当前时间点行不通，以后就没必要尝试这个点了，所以下一次尝试的左端点就可以向右移一移。具体做法是记录一下当前尝试到了那个点，下次就从这个点开始。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn=5010;

int n,now;

int last[maxn],val[maxn],from[maxn],vis[maxn];

long long ans;

struct node

{

	int L,R,v;

}p[maxn];

bool cmpL(const node &a,const node &b)

{

	return a.L<b.L;

}

bool cmpv(const node &a,const node &b)

{

	return a.v>b.v;

}

int dfs(int x,int y)

{

	if(val[y]>p[x].R)	return 0;

	if(!from[y])

	{

		from[y]=x;

		return 1;

	}

	if(p[from[y]].R<p[x].R)	return dfs(x,y+1);

	else	if(dfs(from[y],y+1))

	{

		from[y]=x;

		return 1;

	}

	return 0;

}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

int main()

{

	n=rd();

	int i,j;

	for(i=1;i<=n;i++)	p[i].L=rd(),p[i].R=rd(),p[i].v=rd();

	sort(p+1,p+n+1,cmpL);

	for(i=1;i<=n;i++)	val[i]=max(val[i-1]+1,p[i].L);

	for(i=j=1;i<=n;i++)

	{

		while(j<n&&val[j]<p[i].L)	j++;

		p[i].L=j;

	}

	sort(p+1,p+n+1,cmpv);

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

	{

		now++;

		if(dfs(i,p[i].L))	ans+=p[i].v;

	}

	printf("%lld",ans);

	return 0;

}

收益