????????首先是平凡的邊界。

????????對(duì)于的情形，轉(zhuǎn)移是非常容易的。我們可以不刪除，于是：

????????其中后一項(xiàng)是將全變?yōu)?img type="latex" class="latex" src="http://api.bilibili.com/x/web-frontend/mathjax/tex?formula=0" alt="0">的代價(jià)。另外，此時(shí)我們沒(méi)有任何必要?jiǎng)h除。

????????對(duì)于的情形，我們必須要把它除掉。如果直接刪除，有：

????????如果使用交換，事情稍微復(fù)雜起來(lái)了，我們需要考慮一下交換操作在什么時(shí)候才是有意義的。假設(shè)，且所有的下標(biāo)序列依次序?yàn)?img type="latex" class="latex" src="http://api.bilibili.com/x/web-frontend/mathjax/tex?formula=%5C%7Bi_1%2C...%2Ci_K%5C%7D" alt="%5C%7Bi_1%2C...%2Ci_K%5C%7D">。如果對(duì)交換后進(jìn)行了刪除，那么需要的操作次數(shù)，且與直接刪除完全等價(jià)，因此這種行為是無(wú)意義的。這意味著如果要對(duì)進(jìn)行交換，必須貫徹到底，只對(duì)其使用交換。在這種前提下，為使序列非遞減，假設(shè)需要?jiǎng)h除（），那么僅僅由于帶來(lái)的操作次數(shù)為：

????????如果，那么顯然不如直接將個(gè)全部刪除。

????????如果，這意味著：

????????用人話(huà)說(shuō)就是形成了的一個(gè)子串。這種情況下，直接刪除以及的操作次數(shù)是，并且已經(jīng)合法。如果交換仍然具有意義，那么要求：

????????亦即。換言之，只有在時(shí)，對(duì)和進(jìn)行的交換是可能存在意義的。因此，僅在這一極強(qiáng)的限制滿(mǎn)足時(shí)，我們才進(jìn)行轉(zhuǎn)移：

????????綜上，最終的轉(zhuǎn)移方程為：

????????最后的答案為，總的時(shí)間復(fù)雜度為。

后記

????????代碼很簡(jiǎn)單。如果想看可以去https://github.com/cnzzx/AlgorithmCompetitions