学步园

 1/**//**************************************
 2Problem: POJ 1661 Help Jimmy
 3Time: 16MS
 4Memory: 224K 
 5Accepted Time: 2009-04-09 20:41:34
 6Tips: 《程序设计导引及在线实践》10.4
 7当高度差<=最大高度时, 
 8当前板左边最少时间=min(下一块板的点到左/右边+下一块板左/右边最少时间+高度差)
 9当前板右边最少时间=min(下一块板的点到左/右边+下一块板左/右边最少时间+高度差)
10**************************************/
11#include <stdio.h>
12#include <stdlib.h>
13#define INFINITE 1000000
14struct tag_floor
15{
16    int lx,rx,h,lmin,rmin;
17}floor[1009];
18int mycmp(const void *p1,const void *p2)
19{
20    tag_floor *ptr1,*ptr2;
21    ptr1=(tag_floor *)p1;
22    ptr2=(tag_floor *)p2;
23    return ptr1->h-ptr2->h;
24}
25int main()
26{
27    int tt;
28    scanf("%d",&tt);
29    while(tt--)
30    {
31        int n,x,y,max,i,j;
32        scanf("%d%d%d%d",&n,&x,&y,&max);
33        floor[0].lx=floor[0].rx=x;
34        floor[0].h=y;
35        for(i=1;i<=n;i++)
36        scanf("%d%d%d",&floor[i].lx,&floor[i].rx,&floor[i].h);
37        qsort(floor,n+1,sizeof(tag_floor),mycmp);
38        for(i=0;i<=n;i++)
39        {
40            int left=1,right=1;
41            for(j=i-1;j>=0;j--)
42            {
43                if(left&&floor[j].lx<=floor[i].lx&&floor[i].lx<=floor[j].rx)
44                {
45                    left=0;
46                    if(floor[i].h-floor[j].h>max)floor[i].lmin=INFINITE;
47                    else
48                    {
49                        int ll=floor[i].lx-floor[j].lx+floor[j].lmin+floor[i].h-floor[j].h;
50                        int rr=floor[j].rx-floor[i].lx+floor[j].rmin+floor[i].h-floor[j].h;
51                        if(ll<=rr)floor[i].lmin=ll;
52                        else floor[i].lmin=rr;
53                    }
54                }
55                if(right&&floor[j].lx<=floor[i].rx&&floor[i].rx<=floor[j].rx)
56                {
57                    right=0;
58                    if(floor[i].h-floor[j].h>max)floor[i].rmin=INFINITE;
59                    else
60                    {
61                        int ll=floor[i].rx-floor[j].lx+floor[j].lmin+floor[i].h-floor[j].h;
62                        int rr=floor[j].rx-floor[i].rx+floor[j].rmin+floor[i].h-floor[j].h;
63                        if(ll<=rr)floor[i].rmin=ll;
64                        else floor[i].rmin=rr;
65                    }
66                }
67                if(!left&&!right)break;
68            }
69            if(left)
70            {
71                if(floor[i].h<=max)floor[i].lmin=floor[i].h;
72                else floor[i].lmin=INFINITE;
73            }
74            if(right)
75            {
76                if(floor[i].h<=max)floor[i].rmin=floor[i].h;
77                else floor[i].rmin=INFINITE;
78            }
79        }
80        printf("%d\n",floor[n].lmin);
81    }
82    return 0;
83}
84