机器作业

Description

有n个作业需要在一台机器上执行，一个时刻机器上只能执行一个作业，每个作业可在单位时间内完成，作业i有截止时间di，当作业i在截止时间被执行完，则可获得pi的收益。求最大收益。

Input

第一行输入T(T<=10)表示有T组数据。每组数据先输入一个正整数N(1<=N<=50000)，表示共有N个作业，随后输入N组(di,pi)，表示每个作业的截止时间和收益。

Output

输出T行正整数，第i行表示第i组数据下能获得的最大收益。

解析

初见此题，从搜索的角度看，可以看出这是一个排列树问题，但是排列数问题难以用动态规划等解法使时间复杂度为多项式。我们需要使用某种方法消除“排列”，使这个问题成为一个组合数问题，以便于我们使用动态规划等方法。

可以证明，将最优解中的任务执行顺序按截止时间从小到大排序不会影响最终结果：

对于一个最优的任务执行序列$x_1x_2\dots x_ix_{i+1}\dots x_n$，如果$d_{x_i}>d_{x_{i+1}}$，那么直接交换$x_ix_{i+1}$，使$x_{i+1}$先执行，$x_i$后执行。显然，$i\leq d_{x_{i+1}}<d_{x_i}\leq i+1$，交换后仍然能保证任务执行完成。因此，最优解中的任务执行顺序按截止时间从小到大排序不会影响最终结果。

有了这个结论，我们就可以消除“排列”了。直接将任务执行的顺序固定为截止时间从小到大顺序，在此基础上选择收益最大的任务组合方案即是最优方案。

若排序后的任务顺序为$x_1x_2\dots x_n$，设$f(i,t)$为前$i$个任务在$t$时间内安排产生的最大收益，那么易得状态转移为执行当前任务和不执行当前任务的收益较大的那个：

$f(i,t)=max\{f(i-1,t-1)+p_{x_i},f(i-1,t)\}$

可从$f(0,0)$开始一直计算到$f(n,n)$即得到最终解。