BZOJ2034: [2009国家集训队]最大收益 && BZOJ4276 拟阵+贪心+二分图匹配

这题好强大。

首先，容易证明这是一个拟阵，所以我们按照权值从大到小排序，如果加入当前元素依然合法的话就加入。

那么相当于我们需要判断若干个元素放在一起是否合法。

我们将所有的起点从小到大排序，并对于每个起点找到一个位置不小于起点位置且未被标记过的最小的位置，我们标记这个位置。

利用$O(n)$的时间就能完成标记，并且我们能得到$n$的标记位置。

我们可以证明，我们可以只用这$n$个位置达到一组最优解。

对于每组最优解，我们都可以将选择的时间尽量向前挪，来使得只用到这$n$个位置之一。

每次暴力二分图匹配是$O(n^4)$的。

我们考虑一种贪心的分配方案，依次对于每个关键位置分配任务，每次给这个关键位置分配所有未被分配的、且起点位置不超过当前位置的任务中终点位置最小的。

这样就能用一个堆来进行维护了。

时间复杂度$O(n^2logn)$。

然而并不能过。

我们不好每次都进行一次匹配，所以我们尝试对于原先的匹配加入一个新的任务，看能否合法。

我们从小到大扫描所有的位置，如果这个位置没有分配任务，那么直接分配就行了；否则我们根据贪心进行考虑：

如果新任务的终点位置$<$当前位置分配任务的终点位置，那么让这个位置分配新任务，在这个位置后面去给这个位置原来的任务寻找匹配；

否则在后面的位置给新任务寻找匹配。

不难发现这个过程是$O(n)$。

这样就做到了$O(n^2)$。

代码：

#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;

int getc(){
	static const int L=1<<15;
	static char buf[L],*S=buf,*T=buf;
	if(S==T){
		T=(S=buf)+fread(buf,1,L,stdin);
		if(S==T)
			return EOF;
	}
	return*S++;
}
int getint(){
	int c;
	while(!isdigit(c=getc()));
	int x=c-'0';
	while(isdigit(c=getc()))
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}

#define N 5010
int l[N],r[N],w[N],id[N];
int b[N],m;
int be[N],en[N];

bool cmp(const int&x,const int&y){
	return w[x]>w[y];
}

int tox[N],toy[N];
int _tox[N],_toy[N];

bool dfs(int x,int now,int t){
	if(now>t||now>m-1)
		return 0;
	if(!toy[now]){
		tox[x]=now;
		toy[now]=x;
		return 1;
	}
	if(r[x]<r[toy[now]]){
		if(dfs(toy[now],now+1,en[toy[now]])){
			tox[x]=now;
			toy[now]=x;
			return 1;
		}
		else
			return 0;
	}
	else
		return dfs(x,now+1,t);
}
int main(){
#ifndef ONLINE_JUDGE
	freopen("tt.in","r",stdin);
#endif
	int n=getint(),i,j,k;
	for(i=1;i<=n;++i){
		l[i]=getint();
		r[i]=getint();
		w[i]=getint();
		id[i]=i;
	}
	sort(id+1,id+n+1,cmp);

	for(i=1;i<=n;++i)
		b[i]=l[i];
	sort(b+1,b+n+1);
	for(i=2;i<=n;++i)
		b[i]=max(b[i-1]+1,b[i]);
	m=unique(b+1,b+n+1)-b-1;
	b[++m]=1000000000;

	long long ans=0;

	for(i=1;i<=n;++i){
		be[i]=lower_bound(b+1,b+m+1,l[i])-b;
		en[i]=upper_bound(b+1,b+m+1,r[i])-b-1;
	}
	
	for(i=1;i<=n;++i){
		memcpy(tox,_tox,(n+1)*sizeof(int));
		memcpy(toy,_toy,(n+1)*sizeof(int));
		if(dfs(id[i],be[id[i]],en[id[i]])){
			memcpy(_tox,tox,(n+1)*sizeof(int));
			memcpy(_toy,toy,(n+1)*sizeof(int));
			ans+=w[id[i]];
		}
	}

	cout<<ans<<endl;

	return 0;
}