題意：
? ? ? ? ? ? ? ? ? ? ? ? ? ? 小黑的鎮魂曲


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


思路：

? ? ? 哎！這個題目敲了60多遍，有點傷心了，當時想的是用最短路，因為是1000*1000的坐標，最多也就是1000*1000那么多的點，然后是邊，邊也沒有多少，估計大約600多萬，建邊的話，對于每一個下降，我都建3條邊，當前點到下落點，下落點到下落邊的左端點，下落點到下落邊的右端點（注意一個點下落最多降落在一條邊上，因為無法傳過邊），把能下落的點都mark上，最后在吧所有沒mark并且能到達地面的和地面連接一條邊，跑起點到地面的最短路，結果wa了好多次，后來wa的我自己都蒙了，以為是什么重邊啊什么的（蒙圈了），最后用的dp過的，哎！真心不明白自己的最短路那個地方錯了，這個題目要是用dp還是很同一弄的，和剛接觸dp時的那個數塔差不多，對于每一條邊，我們用他的做端點（和右端點）更新下面的可達邊的左右端點的最優值，dp[i][0]表示的是第i條邊的做端點的最優，dp[i][1]表示的是i條邊右端點的最優，然后就往下更新就行了，記住一點就是一個點下落對多只能降落到一條邊上，所以先sort下，然后第一次降落之后就break，具體看代碼吧。

#include<stdio.h> #include<string.h> #include<algorithm>#define N 1100 #define INF 1000000000 using namespace std;typedef struct {int l ,r ,h; }NODE;NODE node[N]; int dp[N][2];bool camp(NODE a ,NODE b) {return a.h > b.h; }int minn(int x ,int y) {return x < y ? x : y; }bool solve(int n ,int maxx ,int t) {for(int i = 1 ;i <= n ;i ++)dp[i][0] = dp[i][1] = INF;dp[1][0] = dp[1][1] = 0;sort(node + 1 ,node + n + 1 ,camp);for(int i = 1 ;i <= n ;i ++){for(int j = i + 1 ;j <= n ;j ++){if(node[i].h - node[j].h > maxx) break;if(node[i].l >= node[j].l && node[i].l <= node[j].r){ if(j == n){dp[j][0] = minn(dp[j][0] ,dp[i][0] + node[i].h);dp[j][1] = minn(dp[j][1] ,dp[i][0] + node[i].h);}else{dp[j][0] = minn(dp[j][0] ,dp[i][0] + (node[i].h - node[j].h) + (node[i].l - node[j].l));dp[j][1] = minn(dp[j][1] ,dp[i][0] + (node[i].h - node[j].h) + (node[j].r - node[i].l));}break;}} for(int j = i + 1 ;j <= n ;j ++){if(node[i].h - node[j].h > maxx) break;if(node[i].r >= node[j].l && node[i].r <= node[j].r){if(j == n){dp[j][0] = minn(dp[j][0] ,dp[i][1] + node[i].h);dp[j][1] = minn(dp[j][1] ,dp[i][1] + node[i].h);}else{dp[j][0] = minn(dp[j][0] ,dp[i][1] + (node[i].h - node[j].h) + (node[i].r - node[j].l));dp[j][1] = minn(dp[j][1] ,dp[i][1] + (node[i].h - node[j].h) + (node[j].r - node[i].r));}break;}} }return dp[n][0] <= t || dp[n][1] <= t; }int main () {int n ,x ,y ,max ,t ,T ,i;scanf("%d" ,&T);while(T--){scanf("%d %d %d %d %d" ,&n ,&x ,&y ,&max ,&t);node[1].l = node[1].r = x ,node[1].h = y;for(i = 1 ;i <= n ;i ++)scanf("%d %d %d" ,&node[i+1].l ,&node[i+1].r ,&node[i+1].h);n += 2;node[n].l = 0 ,node[n].r = 1001 ,node[n].h = 0;if(solve(n ,max ,t)) printf("NO\n");else printf("YES\n");}return 0; }

?

總結

以上是生活随笔為你收集整理的hdu2155 小黑的镇魂曲(dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

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