从特定的广告牌中删除广告牌

Question

我遇到了这个问题

ADZEN是您所在城市非常受欢迎的广告公司.在每条路上你都可以看到他们的广告牌.最近他们面临着严峻的挑战,MG Road是您所在城市中最常用,最美丽的道路,几乎被广告牌所填满,这对
自然景观产生了负面影响.根据人们的需求,ADZEN已经决定拆除一些广告牌,以便在道路的任何一个区域内放置不超过K个广告牌.你可以假设MG Road是一条带有N个广告牌的直线.最初两个adjecent广告牌之间没有差距.ADZEN的主要收入来自这些广告牌,因此广告牌移除过程必须以这样的方式完成:剩余的广告牌应该在所有可能的最终配置中提供最大可能的利润.配置的总利润是利润值的总和.该配置中存在的所有广告牌.给定N,K和N个广告牌中的每一个的利润值,输出在给定条件下可从剩余广告牌获得的最大利润.

输入说明

第一行包含两个空格分隔的整数N和K.然后按N行描述每个广告牌的利润值,即第i行包含第i个广告牌的利润值.

    Sample Input
    6 2 
    1
    2
    3
    1
    6
    10 

    Sample Output
    21

说明

在给定的输入中有6个广告牌,在此过程之后不应超过2个.因此,删除第一个和第四个广告牌,给出一个利润为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)).