0

我正在从codeforces解决一个问题。

我们的工作是找到使给定整数序列成为非递减序列的最小成本。我们可以在每一步将任意数量的序列增加/减少 1，它将花费 1。

例如，当我们给定一个序列 3, 2, -1, 2, 11，我们可以使该序列不以成本 4 递减（通过递减3到2和递增-1到2，所以非递减序列将是 2, 2 , 2, 2, 11)

根据这个问题的编辑，我们可以用2个序列的动态规划来解决这个问题，（一个是我们给定的序列，另一个是给定序列的排序序列）。

解决方案概要：

如果我们让a是原始序列 并且b是 序列 的排序序列a，并且让f(i,j)是获得前i个元素不递减且第i个元素最多为bj的序列所需的最小移动次数。然后我们可以如下进行递归。（这是来自问题的编辑）

f(1,1)=|a1-b1|
f(1,j)=min{|a1-bj|,f(1,j-1)},  j>1
f(i,1)=|ai-b1|+f(i-1,1),  i>1
f(i,j)=min{f(i,j-1),f(i-1,j)+|ai-bj|},  i>1, j>1

我理解这种重复。但是，我不知道为什么我们应该将原始序列与排序后的序列本身进行比较，并且我不确定我们是否可以使用另一个序列而不是给定序列的排序序列来获得正确的最小成本。

我们如何证明这个解决方案的正确性？我们如何保证排序后的答案是最小成本？

4

1 回答 1

1

练习的重点是可以用归纳法证明这种复发。一旦它被证明，那么我们已经证明这是用th 值f(n,n)最多为 的解决方案结束的最低成本。nbn

要完成对结果的证明，还有一步。这是为了证明任何n超过 th 值的解决方案bn都可以在不增加最大值的情况下得到改进。但这是微不足道的 - 只需从第一个值中省略一个要超过的 +1 bn，您就有了一个更好的解决方案，而没有更大的最大值。因此，没有一个解决方案的最大值大于大于最大值bn的最佳解决方案bn。

因此我们有最优解。

于 2013-06-26T06:22:31.843 回答