从指定广告牌移走广告牌

Question

我碰到了这个问题

ADZEN是一家在你们城市非常受欢迎的广告公司。在每一条路上，你都能看到他们的广告牌。最近，他们面临着一个严峻的挑战，MG路--你们城市中最常用和最美丽的道路--几乎被广告牌填满，这对你的城市造成了负面影响。

自然景观。在市民的要求下，ADZEN已决定移除部分广告牌，以致在道路的任何部分，都不会有多于K个广告牌。你可以假设MG路是一条与N，billboards.Initially的直线，在任何两个形容词的广告牌之间没有空隙。ADZEN的主要收入来自这些广告牌，因此，去除广告牌的过程必须以这样一种方式进行，即在配置的所有可能的最终configurations.Total利润中，剩余的广告牌应该提供最大可能的利润，即该配置中所有广告牌的利润值之和。给定N，K和N个广告牌的利润值，输出在给定条件下剩余广告牌可以获得的最大利润。

输入描述

第1行包含两个独立的整数N和K，然后沿着N条线描述每个广告牌的利润值，即第1行包含第1块广告牌的利润值。

样本输入6 2 1 2 3 1 10样本输出21

说明在给定的输入，有6个广告牌和处理后，不应超过2个应该在一起。因此，删除第一和第四广告牌，使配置_2，3，6，10的利润为21。没有任何其他配置的利润超过21，所以答案是21。

约束1 <= N <= 1,00000(10^5)1 <= K <= N0 <= <= 2000,000,000(2*10^9)

我认为我们必须在第一次k+1板中选择最低成本板，然后重复相同的直到最后，但这并没有给出所有情况的正确答案。我尽我所能，但无法找到解决办法。如果有人有想法，请分享你的想法。

Answer 1

这是一个典型的DP问题。假设P(n，k)是在路上有k块广告牌到n个位置的最大利润。然后你就有了以下公式：

 P(n,k) = max(P(n-1,k), P(n-1,k-1) + C(n))
 P(i,0) = 0 for i = 0..n

其中c(n)是在路上放置第n块广告牌的利润。用这个公式来计算P(n，k)自下而上，你将得到在O(nk)时间内的解。

我让你来弄清楚为什么这个公式成立。

编辑

天，我误解了这个问题。

它仍然是一个DP问题，只是公式不同。假设P(v，i)是指最后一组广告牌尺寸为i的v点的最大利润，那么P(v，i)可以用下列公式来描述：

P(v,i) = P(v-1,i-1) + C(v) if i > 0 
P(v,0) = max(P(v-1,i) for i = 0..min(k, v)) 
P(0,0) = 0

你得找到max(P(n,i) for i = 0..k))。

Answer 2

这个问题是在www.interviewstreet.com上发布的挑战之一。

我很高兴地说，我最近把这件事写下来了，但不太满意，我想看看是否有更好的方法。

soulcheck上面的DP解决方案很简单，但是由于K可以和N一样大，所以不能完全解决这个问题，这意味着在运行时和空间中，DP的复杂度都是O(NK)。

另一种解决方案是进行分支和绑定，跟踪到目前为止的最佳和，如果在某个级别，即如果currSumSoFar + sum (a[currIndex.n)) <= bestSumSoFar .然后立即退出函数，当上限到目前为止无法超过最佳和时，就不再需要进一步处理了。

除2个测试用例外，上述分支和绑定已被测试人员接受.幸运的是，我注意到这两个测试用例使用的是小K(在我的例子中，K< 300)，所以DP技术的O(NK)就足够了。

Answer 3

soulcheck的(第二) DP解决方案在原则上是正确的。使用以下观察结果，您可以进行两项改进：

1)不需要分配整个DP表。你一次只看两行。

2)对于每一行( P(v，i)中的v)，您只感兴趣的是i's，它最大地增加了最大值，这比前一行中保持最大值的每个I多一个。另外，i= 1，否则就不会考虑空白。