PKU2374-Fence Obstacle Course

題目：http://poj.org/problem?id=2374
(請參考原文敘述的"INPUT DETAILS")
我這裡把它想像成SuperMario那樣2D重力的世界
有N(50000)個平台，分別高度是1,2,3,...,N、高度0就是地面
給出這些水平平台在x軸上的左右座標
現在你的起點是無限高空的S
一旦採到空中就會直直的往下掉不能控制
問最少要走水平的幾步，最後才能到達地面的x=0位置？

(我盡力了…好像越來越複雜、還是看原文吧…囧)


程式碼：http://codepad.org/Yy65hZHt
明眼人很容易第一念頭就是DP最強、DP最高，這題DP吧
沒錯，只會往下掉而且決策只有簡單的「選左掉」或「選右掉」
展現了明顯漂量的最優子結構

如何表示狀態呢？
對於某個位置相對低的平台來說，想要掉到這個平台的方式實在是不少種
例如下面這種(x表示平台、o是空氣)
oooooooooxxxo 7
ooooooooxxxoo 6
oooooooxxxooo 5
ooooooxxxoooo 4
oooooxxxooooo 3
ooooxxxoooooo 2
ooxxxxxxxxxxxx 1
以高度1來說，一共有7種不同的掉落法(分別是2左2右、3右、4右…、7右)

透過觀察這個極端的例子可以發現
平台之間、往左會到哪、往右到哪的交互關係其實是確定不變的
就算掉到平台1的方法有7種
實際上至多兩種是有用的：一種是有利於往左跳、一種是有利於往右跳

所以定義DP[平台:{1,2,...,N}][方向:{左,右}]意指目前已知最優的步數，
該步數可以起點->該平台->走到最左側(or最右側)
於是照著高->低(N->1)的順序遍利，更新"該平台往左落點平台"和"該平台往右落點平台"的值

DP的部分想出來了，最後回過頭來看：怎麼計算平台會掉到哪裡？
線段樹阿，就LazyTag技巧自己搜一下吧(被踹)

==================

自己生測資的時候發現這道問題的答案其實很極端
答案的下界是0：一開始就採空直達終點
上界是200000，是什麼情形呢？
當所有平台的聯集就相當於[-100000,100000]全部的時候
起點剛好是0，這樣一定得繞到最左邊、跳到最底、往右走

極端就極端在，中間複雜的決策如果繞太多路的話(通常是random測資...囧)
直接左到底或直接右到底這種無腦方案反而會變成最優方案

所以說也是很值得弄個假解亂搞的一題