Description
给出\(N\)件单位时间任务，对于第\(i\)件任务，如果要完成该任务，需要占用\([S_i, T_i]\)间的某个时刻，且完成后会有\(V_i\)的收益。求最大收益。 澄清：一个时刻只能做一件任务，做一个任务也只需要一个时刻。\(N≤5000\)，\(1 \leq Si \leq Ti \leq 10^8\)，\(1 \leq Vi \leq 10^8\)。
Input
第一行一个整数$N$,表示可供选择的任务个数. 接下来的第二到第$N+1$行，每行三个数，其中第$i+1$行依次为$S_i$，$T_i$，$V_i$
Output
输出最大收益
这道题一开始想用$KM$算法，然而复杂度不太对……想了半天不会做，去膜了FQW的论文后终于会做了……
FQW的论文写得很详细，我在这里也没有必要多说什么了……大概思路就是使用贪心的思想来优化特殊二分图的匹配，先找出$n$个有用的点，然后再把任务按收益从大到小排个序，依次$check$能否选当前这个任务……感觉方法实在是很神……
下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 5010 using namespace std;
typedef long long llg; struct data{
int l,r,x;
}s[maxn];
int pos[maxn],n,pip[maxn];
llg ans; bool cmpl(data a,data b){return a.l<b.l;}
bool cmpx(data a,data b){return a.x>b.x;}
bool work(int x,int d){
if(pos[d]>s[x].r) return 0;
if(!pip[d]){pip[d]=x; return 1;}
else
if(s[pip[d]].r<s[x].r) return work(x,d+1);
else if(work(pip[d],d+1)){pip[d]=x;return 1;}
else return 0;
} int main(){
File("a");
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d %d %d",&s[i].l,&s[i].r,&s[i].x);
sort(s+1,s+n+1,cmpl);
for(int i=1;i<=n;i++) pos[i]=max(pos[i-1]+1,s[i].l);
for(int i=1,j=1;i<=n;i++){
while(pos[j]<s[i].l) j++;
s[i].l=j;
}
sort(s+1,s+n+1,cmpx);
for(int i=1;i<=n;i++) if(work(i,s[i].l)) ans+=s[i].x;
printf("%lld",ans);
return 0;
}