动态规划最优“非递减序列”

Question

问题是，

给定一个具有N个整数的数组A，输出使序列不递减所需的最小操作数。

操作表示在数组Ai中选择一个数字，将其求和为Ai +1或Ai - 1，然后删除Ai

指向问题的链接(西班牙语)：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]。如果Ai的左侧部分已经是非递减的，则如果为A[i] < A[i-1]，则此操作是必需的。

不必要地连接A[i]和A[i+1]会消耗操作，并使连接变得更加困难，所以我们只在必要时才这么做。

• If A[i] < A[i-1]，加入A[i]和A[i+1]，直到A[i] >= A[i-1].
• If

，increment i.

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