http://acm.hdu.edu.cn/showproblem.php?pid=2155經典的DP，很多地方都見到過有類似的題目，一直想A
就像是“是男人就下100層”這個游戲一樣
今天終于A掉了，爽~！
其實這個狀態轉移方程很早的時候就想到了，覺得也不是很難阿，不知道為什么這么少人過。。。
dp[i][0]和dp[i][1]分別記錄起點到臺階i左端右端的最短距離
然后j=i-1
一直找到高度差小于max的臺階j并判斷能不能下降到臺階i
首先處理起點下降到達第一個臺階。
接著就可以寫狀態轉移方程了
hh是記錄臺階的數組
這個是j的左端到達臺階i的方程
右端的把0改成1也相仿
dp[i][0] = Min(dp[i][0],dp[j][0] + hh[j].high - hh[i].high + hh[j].left - hh[i].left);
dp[i][1] = Min(dp[i][1],dp[j][0] + hh[j].high - hh[i].high + hh[i].right - hh[j].left);
最后自己定義
hh[n].high = 0;
hh[n].left = -1;
hh[n].right = 1001;
來表示地面，找到一個最小值和deadline比較。。。YES還是NO就ok了。。。
但是其實一句話讓我找錯找了好久
“當小黑又處于平臺邊緣的時候，他開始繼續下落”
我以為剛剛好掉在平臺邊緣的時候繼續下落不算是在平臺上
判斷能不能到達平臺的語句：
if(hh[end].left<key && key<hh[end].right)
改成
if(hh[end].left<=key && key<=hh[end].right)
才AC。。。。
posted on 2009-02-20 16:00
shǎ崽 閱讀(472)
評論(0) 編輯 收藏 引用