我碰到了这个问题
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)
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个板中选择最低成本的板，然后重复相同的操作直到最后，但这并不能为所有情况提供正确的答案。我尽我所能，但找不到解决方案。如果有任何想法，请分享您的想法。
这是一个典型的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))。
max(P(n,i) for i = 0..k))
