略譯

原題目連結

有 n 個盤子，你很有力氣能拿動任意多盤子，
但礙於你的器用度和平衡感，
你所拿的盤子必須滿足每個盤子都不比上面的任一盤子小，
否則你會摔碎所有盤子。你從第一個盤子走到最後一個，
對每個盤子你可以做以下四件事：

1. 忽略它
2. 若你手上是空的，拿起它
3. 若你手上拿著盤子，你可以把它放到盤子最上方
4. 若你手上拿著盤子，你可以把手上盤子放到盤子上方，再整堆盤子拿起來
   問你走一趟最多可以拿走幾個盤子不摔破

題解

你有一堆盤子，每個盤子可拿可不拿，
拿走時可放盤子頂端或底端，
並且盤子頂只會越來越小、底只會越來越大。

十分顯然的想到 LIS，
但是問題它有兩個方向。

不過當我們決定最初的盤子後，
我們就可以對兩個方向分開 LIS，
除了相同大小的以外它們完全獨立。

相同大小的部份，我們假設有兩個盤子和初始盤子一樣大小，
並且最佳解是一個往上疊，一個往下疊，則我們盤子會長這樣：

初始盤  往上a  往上b  往下a  往下b

這些盤子間可以插任意多雜盤不干擾，假設 初始盤 == 往上a == 往下a
並且 往上b != 往上a、往下b != 往下a，且它是最佳解

則我們發現不管怎麼擺，往上b或往下b其中必定至少有一個在往上a和往下a之後，
所以我們永遠可以把和初始盤相同的歸在同一邊，仍維持最佳解。

歸在哪邊好不一定，那就都試。

所以我們可以枚舉初始盤k，
求 k+1 往上的非嚴格遞增 LIS、k 往下的非嚴格遞減 LIS；
求 k 往上的非嚴格遞增 LIS、k-1 往下的非嚴格遞減 LIS；
並且不能把初始盤丟掉。

n lg m 的 LIS 是可能把初始盤丟掉不使用的。
而 n^2 的 LIS 則必須嚴格讓每個尾，都是從初始盤而來；
也就是每個尾都不能從自己開始。

k+1, k-1 的用意是迴避掉和初始盤相同的情況，
其它大小就算相同，也不會造成重覆計算；
往上和往下會完全獨立開來。

做 n 次 nm 的 LIS 並且剪掉初始盤後全拿也不比當前最佳解好的情況，
1.470 sec AC

進一步加速

從上面解法可知，我們所要計算的是：
決定初始盤後，往下和往上兩個方向的 LIS

我們知道 LIS 狀態是以第 k 個東西為結尾的 LIS 長度，
可是我們要的是以第 k 個東西為起始的 LIS 長度。

那就倒著做吧。

從第 n 個盤子往回做到第 1 個，
在第 k 個盤子時，就變成以盤子 k 為起始的 LIS 長度了。

於是我們從做 n 次 LIS 變成只做 1 次 LIS 就能知道結果。

同樣要注意和初始盤相同大小的情況，以及和初始盤不同時都必須是非嚴格遞增遞減。

n^2 LIS 0.170 sec AC
nm LIS 0.020 sec AC, Rank 1

來自小希的建議

• 試試 [1 2 2 1] 這一組盤子
• 一個比較蠢的方式是拆四組：嚴格/非嚴格、遞增/遞減，共四種組合