问题是,
给定一个包含 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来解决,但是我找不到一个能以小而正确的方式表示问题的状态。
提前致谢。
最佳答案
编辑:我错了。。以下算法不能解决问题。
它可以在一次从左到右的线性扫描中完成。让我解释一下我的推理:
如果你加入两个数字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
范围内,因此明确排除负数,这对算法很重要。
关于arrays - 动态规划最优 "Non-Decreasing Sequence",我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46588228/