Description
给出N件单位时间任务，对于第i件任务，如果要完成该任务，需要占用[Si, Ti]间的某个时刻，且完成后会有Vi的收益。求最大收益。 N≤5000，1 ≤ Si ≤ Ti ≤ 108，1 ≤ Vi ≤ 108。
Analysis
看到题目的第一眼会想到区间DP。。但是这数据范围过于凶残...
第二想法就想到了二分图匹配。左边的节点代表任务，右边的节点代表时刻。但是好像和DP一样，数据范围承受不起...
接着仔细的分析一下，发现右边时刻有许多都是用不到的，最后会用到的，最多只有N个节点！！
我们应该可以通过某种策略找到这N个节点。
最开始的时候，数轴上每一个节点都是可行的，对于每一个节点，我们可以找到在它的时刻范围内最小的且仍然可行的一个点，并添加到右边集合内。
可以证明，利用这N个节点最后构造出的方案就是一种最优方案。（这个证明不会...难道是数学归纳法么？）
接下来我们就可以将S数组排序，线性的扫描出这N个节点。
观察得出右端点集合中，所有时刻是递增的（这个之后会用到）。
然后我们可以通过KM算法来做？
O(N^3)？还是不行！
我们还要继续优化。
我们将任务按价值从大到小排序，依次枚举，若是可以构成匹配则加入ans中，不能则舍去。
上面的那个结论YY一下应该是显然的。
于是我们可以不用做二分图最大权匹配，只用作二分图匹配，匈牙利即可
但是效率仍然是蛋疼的O(N^3)...
考虑继续优化。
刚才我们发现了右端点集合中，所有时刻是递增的。
进而可以得出，每个左端点连向的右端点是一段连续的！
于是我们可以采取一种策略，对于当前的任务，将它之前匹配的任务都尽量往后匹配。
这样每次匹配的效率降到了O(N)，总效率O(N^2)，可以通过了。
具体实现见程序。
var
all,n,m,i,j,last,now:longint;
ans:int64;
st,ed,v,link,re,b:array[1..5010] of longint;
procedure qsort1(l,r:longint);
var
i,j,mid,t,mid2:longint;
begin
i:=l; j:=r; mid:=st[(l+r) shr 1]; mid2:=ed[(l+r) shr 1];
repeat
while (st[i]<mid) or (st[i]=mid) and (ed[i]<mid2) do inc(i);
while (st[j]>mid) or (st[j]=mid) and (ed[j]>mid2) do dec(j);
if i<=j then begin
t:=st[i]; st[i]:=st[j]; st[j]:=t;
t:=ed[i]; ed[i]:=ed[j]; ed[j]:=t;
t:=v[i]; v[i]:=v[j]; v[j]:=t;
inc(i); dec(j);
end;
until i>j;
if i<r then qsort1(i,r);
if j>l then qsort1(l,j);
end;
procedure qsort2(l,r:longint);
var
i,j,mid,t:longint;
begin
i:=l; j:=r; mid:=v[(l+r) shr 1];
repeat
while v[i]>mid do inc(i);
while v[j]<mid do dec(j);
if i<=j then begin
t:=st[i]; st[i]:=st[j]; st[j]:=t;
t:=ed[i]; ed[i]:=ed[j]; ed[j]:=t;
t:=v[i]; v[i]:=v[j]; v[j]:=t;
inc(i); dec(j);
end;
until i>j;
if i<r then qsort2(i,r);
if j>l then qsort2(l,j);
end;
function find(i,x:longint):boolean; //贪心的匹配
var
j:longint;
begin
if b[x]>ed[i] then exit(false);
if link[x]=0 then begin
link[x]:=i;
exit(true);
end;
j:=link[x];
if ed[i]>ed[j] then exit(find(i,x+1))
else begin
if find(j,x+1) then begin
link[x]:=i;
exit(true);
end;
end;
exit(false);
end;
begin
readln(n);
for i:=1 to n do readln(st[i],ed[i],v[i]);
qsort1(1,n);
last:=0;
for i:=1 to n do begin
inc(last);
if st[i]>last then last:=st[i];
inc(m); b[m]:=last;
end;
qsort2(1,n);
b[m+1]:=maxlongint;
for i:=1 to n do begin
for j:=1 to m do
if (st[i]<=b[j]) and (ed[i]>=b[j]) then break;
if find(i,j) then inc(ans,v[i]);
end;
writeln(ans);
end.