algorithm - 解决一系列问题所需的最少天数

Question

您需要完成 N 个编号为 1..N 的问题。您已按难度递增的顺序排列问题，第 i 个问题的估计难度级别为 i。您还为每个问题指定了等级 vi。 vi 值相似的问题本质上是相似的。每天，您将选择问题的一个子集并解决它们。您已经决定，当天解决的每个后续问题都应该比您当天解决的前一个问题更难。此外，为了不让它变得无聊，您解决的连续问题的 vi 等级至少应相差 K。您可以解决所有问题的最少天数是多少？

输入:第一行包含测试用例的数量 T。后面是 T 个测试用例。每个 case 在第一行包含一个整数 N 和 K，然后在第二行包含整数 v1,...,vn。

输出:输出 T 行，每个测试用例一行，包含可以解决所有问题的最少天数。

限制条件:
1 <= T <= 100
1 <= N <= 300
1 <= vi <= 1000
1 <= K <= 1000

示例输入:
2
3 2
5 4 7
5 1
5 3 4 5 6

示例输出:
2
1

这是 interviewstreet 的挑战之一。
以下是我的方法
从第一个问题开始，找出可以解决的最大可能问题数，并将这些问题从问题列表中删除。现在再次从剩余列表的第一个元素开始，直到问题列表的大小为 0。我从这种方法中得到了错误的答案，所以正在寻找一些算法来解决这个挑战。

Answer 1

构造一个 DAG以下方式解决问题。设 p_i 和 p_j 是两个不同的问题。然后，当且仅当 p< sub>j 可以直接 p_i 在同一天连续解决。即，必须满足以下条件:

1. i < j，因为你应该早点解决难度较小的问题。
2. |v_i - v_j| >= K(评级要求)。

现在请注意，选择在某天解决的每个问题子集对应于该 DAG 中的有向路径。你选择你的第一个问题，然后你一步一步地沿着边走，路径中的每条边对应于同一天连续解决的一对问题。此外，每个问题只能解决一次，因此我们 DAG 中的任何节点都可能只出现在一条路径中。而且你必须解决所有的问题，所以这些路径应该覆盖所有的 DAG。

现在我们有以下问题:给定一个 n 个节点的 DAG，找到完全覆盖这个 DAG 的最少数量的非交叉有向路径。这是一个众所周知的问题 Path cover .一般来说，它是NP难的。然而，我们的有向图是非循环的，对于非循环图，它可以在多项式时间内通过减少到 matching problem 来解决。 .反过来，最大匹配问题可以使用 Hopcroft-Karp algorithm 来解决。 ， 例如。确切的减少方法很简单，可以阅读，比如 on Wikipedia .对于原始 DAG 的每个有向边 (u, v) 应该添加一个无向边 (a_u, b_v) 到二分图，其中 {a_i} 和 {b_i} 是大小 n 的两部分。

生成的二分图的每个部分中的节点数等于原始 DAG 中的节点数，n。我们知道，Hopcroft-Karp 算法在最坏情况下的运行时间为 O(n^2.5)，即 300^2.5 ≈ 1 558 845。对于 100测试此算法总共需要不到 1 秒的时间。