所需的天数最少要解决的问题清单(Minimum number of days required to

还有，你需要完成编号1..N N麻烦。你已经按难易顺序增加的问题，第i个问题，估计难度我。您也分配了等级六到每一个问题。类似的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

这是从interviewstreet的挑战之一。
下面是我的方法
从1日开始的问题，并找出最大可能数问题可以解决并从问题这些问题list.Now再次从电量及列表的第一个元素开始，做到这一点到现在的问题列表的大小为0。我得到从这个方法错误的答案，以便寻找一些算法中来解决这一难题。

Answer 1:

构建DAG的按以下方式问题。令p _i和P _j的是两个不同的问题。然后，我们将以此为导向边缘从P _I到P _j的当且仅当P _j的 直接 P上之后可以解决_我在同一天，连续。也就是说，下列条件必须满足：

我置于<J，因为你应该早点解决少的难题。
| V _I - _vĴ| > = K（评级要求）。

现在可以看到的是选择在某一天所要解决的问题每个子集对应于在DAG 定向路径 。你选择你的第一个问题，然后你按照边一步一步，路径中的每个边缘对应于对问题已经解决了连续在同一天。此外，每个问题可以解决只有一次，所以在我们的DAG任何节点可能只出现在只有一个路径。而且你必须解决所有的问题，所以这些路径应涵盖所有的DAG。

现在，我们有以下的问题：给定n个节点的DAG，发现不相交的最小数量指示，完全覆盖此DAG路径。这是一个众所周知的问题称为道盖。一般来说，它是NP难。但是，我们有向图是无环，并为无环图可以在多项式时间内使用减少到要解决匹配问题。最大匹配问题，反过来，可以通过使用解决霍普克洛夫特-卡普算法，例如。确切的还原方法简单，可以读，讲，在维基百科上。对于每一个有向边（U，V）的原DAG之一应该添加的无向边（ _コ ，B _v）进行二分图，其中{A _I}和{B _I}是大小为n的两个部分。

在所得的二分图的各部分的节点的数量等于在原始DAG的节点的数量，N。 我们知道，霍普克洛夫特-卡普算法为O在最坏的情况下（N ^2.5）运行，300 ^2.5≈1 558 845 100个对于测试这种算法应该采取下一个总额1秒。

Answer 2:

该算法简单。首先，排序的问题v_i ，那么，对于每个问题，发现在间隔的问题数量(v_i-K, v_i]这些号码的最大是结果。第二阶段可以在完成O(n) ，因此最昂贵的操作是排序，使得整个算法O(n log n) 。看看这里的算法的工作对你的数据，并在电子表格中K = 35的演示。

为什么这项工作

让我们重新制定的问题图着色的问题。我们创建图G如下：顶点将成为问题，而且会有两个问题IFF之间的边缘|v_i - v_j| < K |v_i - v_j| < K

在这样的曲线图中，独立设置的完全对应于套在同一天可行的问题。（<=）如果该组可以在一天内进行，这肯定是独立设置的。（=>）如果设置不包含两个问题不能满足K-差条件，您可根据困难只是对它们进行排序和顺序解决这些问题。这两个条件将得到满足这种方式。

因此，很容易得出，图G的着色完全对应的在不同的日子的问题时间表，与对应于一个每天每只颜色。

所以，我们要找出图形的色度，一旦我们认识到图形是一个区间图，这是一个完美的图形，那些具有色度等于cliqueness G.这将是容易的，都可以通过一个简单的算法找到。

间隔图是在实线间隔的曲线图，边缘相交间隔之间。我们的图，是可以很容易地看出，是一个间隔曲线图（对于每个问题，分配的时间间隔(v_i-K, v_i]它可以很容易地看出，该间隔图的边是正是我们的图的边）。

引理1：在一个时间间隔曲线图中，存在一个顶点，其邻居形成集团。

证明是容易的。你只需要与所有的最低上限（或最高下界）的时间间隔。任何交叉它间隔有上限越高，因此，结合的所述第一区间的上被包含在它们所有的交叉点。因此，它们彼此相交而形成集团。 QED

引理2：在图族的封闭诱导子图，并具有从引理1（顶点的存在，它的邻居形成集团）的性质，以下的算法产生最小着色：

查找顶点X，其邻居形成一个集团。
从图中删除的x，使得它的子图G”。
G色的”递归
以最少的颜色颜色X对邻国没有找到

证明：在（3）中，算法产生子图G”通过感应假说+我们对诱导的子图家族的紧密最佳的着色。在（4）中，算法只选择一个新的颜色n如果有大小的集团n-1 x的邻居。这意味着，其中x，有大小的集团n在G，所以它的色度必须至少n 。因此，通过该算法给一个顶点的颜色总是<= chromaticity(G)这意味着着色是最佳的。（显然，该算法产生一个有效的着色）。 QED

推论：间隔图是完美的（完美<=>色度== cliqueness）

所以，我们只需要找到G的cliqueness即能轻松从容的时间间隔图：你刚才处理实线不包含间隔边界和计数间隔交叉出现的数量，而你的情况，在那里更容易段间隔具有均匀的长度。这导致了这个文章的开头列出的算法。