带权活动选择

Description

给定$n$个活动，活动$a_i$表示为一个三元组$(s_i,f_i,v_i)$，其中si表示活动开始时间，fi表示活动的结束时间，$v_i$表示活动的权重, $s_i<f_i$。带权活动选择问题是选择一些活动，使得任意被选择的两个活动$a_i$和$a_j$执行时间互不相交，即区间$[s_i,f_i)$与$[s_j,f_j)$互不重叠，并且被选择的活动的权重和最大。请设计一种方法求解带权活动选择问题。

Input

第一行输入$M(M\leq 10)$表示有$M$组数据。每组数据输入整数$N(N\leq 10000)$, 接下来输入$N$个活动。

Output

输出$M$行正整数，第i行表示第i组数据的能够选择活动最大权值和。

解析

和01背包问题类似，使用动态规划方法。

首先将活动按结束时间顺序进行排序。定义从最早结束的活动到第$i$个结束的活动的最优排列方案为$f(i)$，与结束时间早于$s$的活动集合的最优排列方案为为$g(s)=f(j)(f_j\leq s)$，那么$f(i)$满足最优子结构特性：

$f(i)=max\{f(i-1),g(s_i)+v_i\}$

显然，$f(i)$的重叠子问题集合为：

$\{f(i)|1\leq i\leq n\}$

空间复杂度为$o(n)$，每个子问题都只需要计算其之前的两个值，因此时间复杂度为$O(n)$，再加上开始时的排序时间，时间复杂度为$O(nlog\ n)$