题目简述

给定长度为的串，每次操作可以删除任意元素（代价为）或交换相邻元素的位置（代价为）。求将该串变为非递减串的最少的代价（空串也是非递减的）。

原题目链接：https://codeforces.com/contest/1809/problem/D

(资料图片仅供参考)

思路

每次操作代价的数值是最扎眼的。足够大并且足够小的奇怪数值，保证了：无论进行的操作种类如何，总操作次数越少越好。这是因为至多次删除就一定能把串变成非递减的，而此时（差异凑不够一次操作），因此操作次数在优化中占据了绝对的主导地位。

另一个简单的事实是，非递增串的前缀必然也是非递增的。如此优良的性质，不令表示将变为以不以结尾的非递增序列所需的最小代价，是很不划算的。（以结尾则是平凡的，答案是，其中表示中的数目。）

首先是平凡的边界。

对于的情形，转移是非常容易的。我们可以不删除，于是：

其中后一项是将全变为的代价。另外，此时我们没有任何必要删除。

对于的情形，我们必须要把它除掉。如果直接删除，有：

如果使用交换，事情稍微复杂起来了，我们需要考虑一下交换操作在什么时候才是有意义的。假设，且所有的下标序列依次序为。如果对交换后进行了删除，那么需要的操作次数，且与直接删除完全等价，因此这种行为是无意义的。这意味着如果要对进行交换，必须贯彻到底，只对其使用交换。在这种前提下，为使序列非递减，假设需要删除（），那么仅仅由于带来的操作次数为：

如果，那么显然不如直接将个全部删除。

如果，这意味着：

用人话说就是形成了的一个子串。这种情况下，直接删除以及的操作次数是，并且已经合法。如果交换仍然具有意义，那么要求：

亦即。换言之，只有在时，对和进行的交换是可能存在意义的。因此，仅在这一极强的限制满足时，我们才进行转移：

综上，最终的转移方程为：

最后的答案为，总的时间复杂度为。

后记

代码很简单。如果想看可以去https://github.com/cnzzx/AlgorithmCompetitions

标签：