有关如何根据给定条件找到标记给定数组的所有元素的最小步数的任何提示？
给出了两个整数N<=10^5和K<=N ，其中N是数组A[]的大小， K是我们在过程中可以选择的连续子序列的长度。 A[i]<=10^9元素A[i]<=10^9 。 现在假设最初所有数组元素都没有标记。 在每个步骤中，我们将选择长度为K任何子序列，如果此子序列具有未标记的元素，那么我们将标记所有未标记的元素，这些元素在后序中是最小的。 现在如何计算标记所有元素的最小步数？
为了更好地理解问题，请参阅此示例 –
N=5 K=3 A[]=40 30 40 30 40
步骤1-选择区间[1,3]并标记A [1]和A [3]
步骤2 – 选择区间[0,2]并标记A [0]和A [2]
步骤3-选择区间[2,4]并标记A [4]
因此，此处的最小步骤数为3。
我的方法（速度不够快） –
我从数组的第一个元素开始，并在距离<=K处标记所有未标记的元素，并将steps递增1。
首先考虑如何回答K == N的问题（即对子序列的长度没有任何有效的限制）。 您的答案应该是最小步数是数组中不同值的数量。
然后考虑当K减小时这会如何变化; 重要的是，对于A存在的每个值n ，需要覆盖选择集{i: A[i] == n}的K长度间隔的副本数量。 沿着A行走K长度间隔的朴素算法，在n该值处尚未覆盖的每个位置A[i]处停止是完全足够的。
当我们看到最小步数= N / k或N / k + 1并且最大步数=（n + k-1）。 我们必须优化步骤的总数，这取决于我们所做的选择的过去历史，这是指动态解决方案。
有关动态理论教程，请参阅http://www.quora.com/Dynamic-Programming/How-do-I-get-better-at-DP-Are-there-some-good-resources-or-tutorials-on-it样最TopCoder的教程上-DP /答案/米哈尔- DANIL％C3％A1K
可以在O（n）中解决如下：跟踪每个元素a [i]。 如果a [i]之前未跟踪，则映射数字及其索引并增加计数器。如果先前跟踪了数字，则检查其（最后一个index-curr_index）> = K，如果是，则更新索引并增加计数。 打印计数。 地图STL将是有益的。