題目描述

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

吐槽

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

算法分析

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