您需要完成编号为1..N的N个问题。您已经按难度递增的顺序排列了问题，第i个问题的估计难度为i。您还为每个问题分配了评级vi。vi值相似的问题本质上是相似的。每天，您将选择一部分问题并加以解决。您已经决定，当天要解决的每个后续问题都比当天要解决的上一个问题要困难。另外，为了避免感到无聊，您要解决的连续问题在Vi评分上的差异应至少为K。可以解决所有问题的最少天数是多少？
输入：第一行包含测试用例T的数量。后面是T个测试用例。每个案例的第一行都包含整数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
这是来自采访街的挑战之一。 下面是我的方法， 从第一个问题开始，找出最大可能解决的问题并将这些问题从问题列表中删除。现在再次从剩余列表的第一个元素开始，直到现在问题列表的大小为0我从这种方法得到了错误的答案，因此正在寻找一些算法来解决这一挑战。
通过以下方式构造问题的DAG。令 p i_和 _p j_是两个不同的问题。然后，当且仅当 _p j 可以 在* p i 之后 的同一天 直接 连续求解时，我们才会从 _p i_到 _p j_绘制有向边。即，必须满足以下条件： __ *__
现在注意，选择在某天解决的问题的每个子集都对应于该DAG中的 定向路径 。您选择第一个问题，然后逐步进行操作，路径中的每个边缘对应于在同一天连续解决的一对问题。同样，每个问题只能解决一次，因此DAG中的任何节点都只能出现在一条路径上。而且您必须解决所有问题，因此这些路径应涵盖所有DAG。
现在，我们面临以下问题：给定 n个 节点的DAG ，找到完全覆盖此DAG的最少数量的非交叉定向路径。这是一个众所周知的问题，称为Path cover。一般来说，它是NP难的。但是，我们的有向图是非 循环的 ，对于非循环图，它可以使用匹配问题的归约在多项式时间内求解。反过来，最大匹配问题可以使用例如Hopcroft- Karp算法解决。确切的归约方法很容易，例如可以在Wikipedia上阅读。对于原始DAG的每个有向边 （u，v） ，应添加无向边 （a u， b v）_到二部图，其中 和 是大小 _n的 两个部分。
生成的二分图的每个部分中的节点数等于原始DAG中的节点数 n 。我们知道，在霍普克洛夫特-卡普算法运行 _为O（n 2.5），_在最坏的情况下，和300 2.5 ≈1 558 845 100对于测试这种算法应该采取下一个总额1秒。
