POJ 1661

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 
 4 int dp[1010][2],N,max1;
 5 
 6 struct In{          
 7     int h;
 8     int lx;
 9     int rx;
10 }s[1009];         
11 
12 int cmp(const void *a,const void *b)
13 {
14     return (*(In *)a).h-(*(In *)b).h;
15 }
16 int Min1(int x,int y)
17 {
18     return (x<y)?x:y;
19 }
20 
21 void turnleftmintime(int i)
22 {
23     int k=i-1;        
24     while(k>0&&s[i].h-s[k].h<=max1)       //由于是从下面往上面走，所以呢，第一层肯定不在地上，因为在地上不需要移动距离，只需要跳上去的时间便可，且上一层一下一层的距离肯定要小于最大距离
25     {
26         if(s[i].lx>=s[k].lx&&s[i].lx<=s[k].rx)　　　　　　//这个就是那个图示的意思了，s[i].lx>=s[k].lx代表着下一层的左边肯定要在上一层左边的左边，意思就是上一层的左边肯定要大于下一层的右边
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//且上一层的左边肯定也要在下一层的右边的左边，不然没有交集跳不上，如果上一层不符合的话，那么从下下一层在试，因为上一层肯定是要用到的，

27         {
28            dp[i][0] = s[i].h-s[k].h+Min1(s[i].lx-s[k].lx+dp[k][0],s[k].rx-s[i].lx+dp[k][1]);     //dp[i][0]是用来存从左边开始往上跳到第i层的最短时间，而其它的时间就是等于距离差加上，从左边上和从右边上的时间，选择时间短的。
29 
30 
31             return;
32         }
33         else k--;
34     }
35     if(s[i].h-s[k].h>max1)              //这个就是考虑前几层都不符合条件的情况下还有跳第一层时的情况
36         dp[i][0]=999999;
37     else dp[i][0]=s[i].h;       
38 }
39 
40 void turnrightmintime(int i)
41 {
42     int k=i-1;
43     while(k>0&&s[i].h-s[k].h<=max1)
44     {
45         if(s[i].rx<=s[k].rx&&s[i].rx>=s[k].lx)
46         {
47             dp[i][1]=s[i].h-s[k].h+Min1(s[i].rx-s[k].lx+dp[k][0],s[k].rx-s[i].rx+dp[k][1]);
48             return;
49         }
50         else k--;
51     }
52     if(s[i].h-s[k].h>max1)
53         dp[i][1]=999999;
54     else dp[i][1]=s[i].h;
55 }
56 
57 int shorttime()
58 {
59     int i;
60     for(i=1;i<=N+1;i++)
61     {
62         turnleftmintime(i);
63         turnrightmintime(i);
64     }
65     return Min1(dp[N+1][0],dp[N+1][1]);
66 }
67 
68 int main()
69 {
70     int n,x,y;
71     scanf("%d",&n);
72     while(n)
73     {
74         n--;
75         scanf("%d%d%d%d",&N,&x,&y,&max1);
76         for(int i=1;i<=N;i++)
77             scanf("%d%d%d",&s[i].lx,&s[i].rx,&s[i].h);
78         s[0].h=0;                //这个的目的就是用于跳第一层，除了h有用，其他两个值都没用的
79         s[0].lx=-20000;
80         s[0].rx=20000;
81         s[N+1].h=y;
82         s[N+1].lx=x;　　　　　　　　//这个就是目标地点
83         s[N+1].rx=x;
84         qsort(s,N+1,sizeof(s[0]),cmp);
85         printf("%d\n",shorttime());
86     }
87     return 0;
88 }