arrays - 动态规划最优 "Non-Decreasing Sequence"

Question

问题是，

给定一个包含 N 个整数的数组 A，输出使序列不递减所需的最少操作次数。

一个操作表示在数组A[i]中选择一个数，将其与A[i + 1]或A[i - 1]相加，并删除A[i]

问题的链接(西类牙语):https://omegaup.com/arena/problem/Torres#problems

例子:

3
5 2 1

Answer: 2

在这种情况下，我们必须加入所有数字，将序列变为 { 8 }，这是非递减的

限制:

N <= 5000
A[i] <= 10^5

我认为这个问题可以用DP来解决，但是我找不到一个能以小而正确的方式表示问题的状态。

提前致谢。

Answer 1

编辑:我错了。。以下算法不能解决问题。

它可以在一次从左到右的线性扫描中完成。让我解释一下我的推理:

如果你加入两个数字A[i]和 A[i+1] , 结果大于 A[i] .如果A[i]左边的部分已经是非递减的，如果A[i] < A[i-1]，这个操作是必须的.

不必要的加入A[i]和 A[i+1]消耗一个操作并使连接的事情变得更加困难，所以我们只在必要时才这样做。

• 如果A[i] < A[i-1] , 加入 A[i]和 A[i+1]直到 A[i] >= A[i-1] .
• 如果A[i] >= A[i-1] , 递增 i.

附言原始问题描述指出 A[i]在 1...10^5 范围内，因此明确排除负数，这对算法很重要。