相关疑难解决方法(0)

我遇到了这个问题

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

Run Code Online (Sandbox Code Playgroud)

说明

在给定的输入中有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)

Run Code Online (Sandbox Code Playgroud)

我认为我们必须在第一个k + 1板中选择最低成本板然后重复相同的直到最后,但这并没有给出所有情况的正确答案.我尝试了我的知识,但无法找到解决方案.如果有人有想法,请分享你的想法.