題目描述

   N個按鈕在一條直線上排列，給出每個按鈕的坐標(Xi,0)。每個按鈕按下之后在Ti秒之后馬上彈起，你一開始在最左端的按鈕上，每移動1個單位長度需要1秒鐘。
   請問你能否在某一時刻使所有按鈕都是按下的。如果可以輸出任一方案。

吐槽

   hdu 4053是同樣的題目，但是spj不好用啊啊啊啊啊......

算法分析

   不仔細想是不會想到用動態規劃的，因為沒有重疊子問題啊...
   但是有一個比較重要的性質：如果你要按下某個區間[left,right]的按鈕，那么一定是從端點開始按的...
   對于一個區間，如果你選擇了先按某點k，那么你一定要經歷一個left到right或者right到left的過程。
   在這個過程中，完全有按下k的機會。所以先按k就浪費了...
   K的確可能是最優的，但是先按端點一定不會比K差 這樣的話就可以DP了。
   于是狀態就可以表示成dp[left][right][p]，p=0和p=1分別表示從左端或者從右端進入區間[left,right]花費的最小時間。
   決策分兩種 ： 按下左端點，那么就從左端進入區間[left+1,right]。并判斷T[l]是否大于dp[left+1,right,0]+cost[l,l+1]。 按下右端點同理。
   然后記錄一下這個區間的最優決策。DP完之后就可以遞歸的輸出決策了，輸出時有個trick： 行尾不要有額外的空格。
   解決辦法也很簡單：區間[i,i]一定是最后進入的，也就是最后輸出的決策。
   代碼參照shi哥的吧...