这是一个典型的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))。
