hdu2155 小黑的鎮魂曲(dp)

題意：

                            小黑的鎮魂曲

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;
}