本文共 1399 字，大约阅读时间需要 4 分钟。

方伯伯想通过最多K次区间拔高，将玉米的高度调整为单调不下降序列。我们可以使用动态规划来解决这个问题。

方法思路

我们定义 dp[i] 为前 i 棵玉米处理完毕后，满足单调不下降条件的最大保留数目。对于每一棵第 i+1 棵玉米，我们需要确保前 i 棵玉米的高度不超过当前玉米的高度 a[i+1]。为了实现这一目标，我们需要计算前 i 棵玉米在最多 K 次拔高后的最大可能高度，并确保它不超过 a[i+1]。

具体步骤如下：

解决代码

import sysdef main():    n, K = map(int, sys.stdin.readline().split())    a = list(map(int, sys.stdin.readline().split()))    a = [0] + a  # 1-based index    max_dp = [0] * (n + 1)    for i in range(1, n + 1):        max_dp[i] = 1  # 至少保留当前玉米        for j in range(i):            if a[j] + K >= a[i]:                if max_dp[j] + 1 > max_dp[i]:                    max_dp[i] = max_dp[j] + 1            else:                # 计算前j棵在K次拔高后的最大可能高度                # 这里用简单的预处理，取前j棵的最大值                current_max = 0                for k in range(j):                    if a[k] + K > current_max:                        current_max = a[k] + K                if current_max <= a[i]:                    if max_dp[j] + 1 > max_dp[i]:                        max_dp[i] = max_dp[j] + 1        print(max_dp[i])    print(max_dp[n])if __name__ == "__main__":    main()

代码解释

这个方法通过动态规划和预处理，确保在最多 K 次操作下，找到最长的单调不下降序列。

转载地址：http://nbcq.baihongyu.com/