从给定的广告牌上删除广告牌

Question

我碰到了这个问题

ADZEN是您所在城市非常受欢迎的广告公司。在每条路上，您都可以看到他们的广告广告牌。最近，他们面临着严峻的挑战，MG
Road是您所在城市中最常用和最美丽的道路，几乎被广告牌填满，这对
自然的看法。在人们的需求下，ADZEN决定拆除某些广告牌，以使道路的任何部分最多只能放置K个广告牌。您可以将MG
Road假定为具有N个广告牌的直线。最初，两个相邻的广告牌之间没有空隙。ADZEN的主要收入来自这些广告牌，因此，广告牌移除过程必须以这样的方式进行：剩余的广告牌应在所有可能的最终配置中提供最大可能的利润。配置的总利润是的总利润。该配置中存在的所有广告牌。给定N，K和N个广告牌中每个广告牌的利润值，

输入说明

第一行包含两个以空格分隔的整数N和K。然后在N行中描述每个广告牌的利润值，即，第一行包含第i个广告牌的利润值。

    Sample Input
    6 2
    1
    2
    3
    1
    6
    10

    Sample Output
    21

说明

在给定的输入中，有6个广告牌，并且在该过程之后，最多不能有2个在一起。因此，删除第一个广告牌和第​​四个广告牌，获得配置_ 2 3 _ 6
10的利润为21。没有其他配置的利润大于21。因此答案为21。

    Constraints
    1 <= N <= 1,00,000(10^5)
    1 <= K <= N
    0 <= profit value of any billboard <= 2,000,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))。