主题

主题

 
   

4276: [ONTAK2015]Bajtman i Okrągły Robin

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=4276

Description

有n个强盗,其中第i个强盗会在[a[i],a[i]+1],[a[i]+1,a[i]+2],...,[b[i]-1,b[i]]这么多段长度为1时间中选出一个时间进行抢劫,并计划抢走c[i]元。

作为保安,你在每一段长度为1的时间内最多只能制止一个强盗,那么你最多可以挽回多少损失呢?

Input

第一行包含一个正整数n(1<=n<=5000),表示强盗的个数。

接下来n行,每行包含三个正整数a[i],b[i],c[i](1<=a[i]<b[i]<=5000,1<=c[i]<=10000),依次描述每一个强盗。

Output

输出一个整数,即可以挽回的损失的最大值。

Sample Input

4

1 4 40

2 4 10

2 3 30

1 3 20

Sample Output

90


个人解法:

比较奇怪的题目大意。事实上是说你可以选择安排强盗的抢劫事件来最大化你可以挽回的损失。

那么我们考虑带权二分图匹配。把强盗和时间匹配即可。

边可能会达到O(n^2)。

考虑使用一棵线段树。树边均为<vol=none,cost=0>(none为正无穷),每一个点只需要向对应的区间的O(logn)个节点连边即可。

这样边数变为了O(nlogn)。


代码如下:

https://code.csdn.net/snippets/2237389

 
 
评论