小黑的鎮魂曲

Time Limit: 5000/2000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Problem Description 這個事情發生在某一天，當小黑和SSJ正在約會的時候，邪惡的Guner抓走了SSJ，小黑傷心萬分，怒不可遏啊！但是他顯然也是沒有辦法的，誰叫Guner比小黑邪惡，小黑打不過Guner呢！
于是，小黑利用皮膚保護色，趁夜摸黑前往Guner的城堡，準備偷偷摸摸的把SSJ拯救出來，但是只要小黑一打開SSJ身上的鎖鏈，看門的蔥頭就會在M秒以內通知Guner，Guner馬上超時空轉移，閃到小黑身邊抓住他們，于是小黑雖然跑得不快，但是他也不得不跑啊。
由于Guner的城堡構造特殊，它是由一個一個的平臺搭建成的，所以小黑的逃跑路線是這樣的，在時刻0的時候，他位于最高點，也就是高于所有的平臺，然后他開始垂直下落，他的下落速度是1米/秒。當小黑下落到某個平臺上時，他可以向左跑也可以向右跑，他的跑動速度還是1米/秒。當小黑又處于平臺邊緣的時候，他開始繼續下落。但是小黑是個憐香惜玉的人，為了顧及懷中的SSJ，于是他每次下落的最大高度不會超過MAX米，不然SSJ摔壞了，Guner也懶得追了，小黑也會傷心致死的。但是只要小黑抱著SSJ一落到地面，Guner就再也抓不住他們了。



Input 第一行輸入一個數T(0 < T <= 10)，表示測試數據的組數。每組測試數據的第一行是5個整數，N,X,Y,MAX,M,用空格分開。N(0 < N <= 1000)是臺階的數目，X,Y分別是小黑0時刻所在位置的橫、縱坐標，MAX表示小黑最多能下落的高度，M表示從小黑一打開鎖鏈蔥頭發覺后報告給Guner的時間，接下來有N行數據，每行數據描述一個臺階，包括3個數據，Xl[i],Xr[i],H[i],其中Xl[i](0 < Xl[i] <= 1000)表示當前臺階最左邊的邊的X坐標，Xr[i](0 < Xr[i] <= 1000)表示當前臺階最右邊的邊的X坐標，H[i](0 < H[i] < 1000)表示當前臺階離地面的高度。數據確保小黑和SSJ是能到達地面的。
Output 每組測試數據當Guner能抓住小黑和SSJ時，輸出YES，否則輸出NO.
Sample Input 1 1 10 17 20 20 1 8 7
Sample Output NO解題思路：這道題目是一個比較明顯的DP，這里把整個平面看成一個二維坐標系，那么就很好列出狀態方程，設dp[i][j]為到坐標為（i，j）的點時，所需要最短的時間（其實就是走的距離）。那么狀態方程就是：dp[xr][j-k] = min{dp[i][j]+k+xr-i},dp[xl][j-k] = min{dp[i][j]+k+i-xl} (表示從(i,j)處落下，到臺階兩側的距離)。k是從1-MAX枚舉的，表示落下的高度是k。那么這個算法就需要三層循環，最外面兩層枚舉坐標點，最里面一層從1-MAX枚舉下落的高度。。此外，這里在判斷某一個高度時是否有臺階可以降落，可以用hash來記錄。。。 AC:#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 1005; const int inf = 0x3f3f3f3f; int n,m,x,y,MAX,cnt,minx,maxx; int dp[maxn][maxn],h[maxn]; struct Node {int xl,xr,h;int next; }node[maxn];void init() {memset(dp,-1,sizeof(dp));memset(h,-1,sizeof(h));cnt = 0;minx = inf;maxx = 0; }void add(int XL,int XR,int H) {int t = h[H];node[cnt].xl = XL;node[cnt].xr = XR;node[cnt].h = H;node[cnt].next = -1;if(t == -1)h[H] = cnt++;else{node[cnt].next = t;h[H] = cnt++;} }int search(int H,int X) //返回節點編號 {int t = h[H];while(t != -1){if(node[t].xl <= X && node[t].xr >= X)return t;t = node[t].next;}return -1; }void solve() {//先找到落在的第一塊板上int hei;for(hei = 0; hei <= MAX; hei++){int t = search(y-hei,x);if(t != -1){dp[node[t].xl][y-hei] = hei + x-node[t].xl;dp[node[t].xr][y-hei] = hei + node[t].xr - x;break;}}for(int j = y-hei; j >= 0; j--)for(int i = maxx; i >= minx; i--)for(int k = 1; k <= MAX; k++){if(dp[i][j] == -1) break;if(j - k == 0){dp[i][0] = dp[i][j] + k;break;}int t = search(j-k,i);if(t == -1) continue;if(dp[node[t].xl][j-k] == -1)dp[node[t].xl][j-k] = dp[i][j] + k + i - node[t].xl;else dp[node[t].xl][j-k] = min(dp[node[t].xl][j-k],dp[i][j] + k + i - node[t].xl);if(dp[node[t].xr][j-k] == -1)dp[node[t].xr][j-k] = dp[i][j] + k + node[t].xr - i;else dp[node[t].xr][j-k] = min(dp[node[t].xr][j-k],dp[i][j] + k + node[t].xr - i);break;}int ans = inf;for(int i = 0; i <= 1000; i++)if(dp[i][0] != -1)ans = min(ans,dp[i][0]);if(ans > m) cout<<"YES"<<endl;else cout<<"NO"<<endl; }int main() {int t;cin>>t;while(t--){init();cin>>n>>x>>y>>MAX>>m;for(int i = 1; i <= n; i++){int XL,XR,H;cin>>XL>>XR>>H;minx = min(minx,XL);maxx = max(maxx,XR);add(XL,XR,H);}solve();}return 0; }

總結

以上是生活随笔為你收集整理的hdu 2155（dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。