pku1334 Two Mountaineers 贪心+分类讨论

题意:

两个人爬山,时刻要保证在同一水平面上,直到两人互换位置。问走过的最短距离。两点间距离定义为两点间的y轴绝对值差。
给力条件:除了首尾两点每个点的y坐标均不相同

解法:
DP?杀鸡用牛刀,没必要!
贪心!
首先明确,不能走回头路,这里的回头路指完全退回到上个步骤所在的点,显然,这样的走法是无意义的。
设置两个指针,p1指向头,p2指向尾,循环至两个指针重叠。下面具体分四种情况讨论:
1、如果yp1+1>yp1且yp2-1>yp2,这种情况下当然山峰高的帮助山峰低的越过低的山峰

2、如果yp1+1>yp1且yp2-1<yp2,这种情况又要分两种情况:
      2.1 如果(p1,p1+1)这段上坡通过局部回退能够让p2度过这个山谷,显然这样就是p2--
      2.2 否则p1必须回退至上个拐点,试图获得更低的高度,这样就是p1--
3、如果yp1+1<yp1且yp2-1>yp2,与上种情况类似,不加赘述。
4、如果yp1+1<yp1且yp2-1<yp2,这种情况不应该是正常情况下应该出现的,因该是碰到某个很深的山谷后上坡段回退形成的,这时候应该继续后退,以寻求更低点。

代码里写的很清楚,大家看代码吧:
 1# include <cstdio>
 2using namespace std;
 3# define min(a,b) ((a)<(b)?(a):(b))
 4# define max(a,b) ((a)>(b)?(a):(b))
 5int p[1001][2],n,p1,p2,ans,last;
 6int main()
 7{
 8    int test;
 9    scanf("%d",&test);
10    while(test--)
11    {
12        scanf("%d",&n);
13        for(int i=0;i<n;i++)
14          scanf("%d %d",&p[i][0],&p[i][1]);
15        p1=0,p2=n-1,ans=0;
16        last=p[0][1];
17        while(p2>p1)
18        {
19           if(p[p2-1][1]>p[p2][1]&&p[p1+1][1]>p[p1][1])
20           {
21                ans+=2*(min(p[p2-1][1],p[p1+1][1])-last);
22                last=min(p[p2-1][1],p[p1+1][1]);
23                if(p[p2-1][1]==last) p2--;
24                if(p[p1+1][1]==last) p1++;
25           }

26           else if(p[p2-1][1]<p[p2][1]&&p[p1+1][1]>p[p1][1])
27           {
28              ans+=2*(last-max(p[p2-1][1],p[p1][1]));
29              last=max(p[p2-1][1],p[p1][1]);
30              if(last==p[p2-1][1]) p2--;
31              else p1--;
32           }

33           else if(p[p2-1][1]>p[p2][1]&&p[p1+1][1]<p[p1][1])
34           {
35            ans+=2*(last-max(p[p2][1],p[p1+1][1]));
36            last=max(p[p2][1],p[p1+1][1]);
37            if(last==p[p1+1][1]) p1++;
38            else p2++;
39           }

40           else
41           {
42              ans+=2*(min(p[p1][1],p[p2][1])-last);
43              last=min(p[p1][1],p[p2][1]);
44              if(last==p[p1][1]) p1--;
45              else p2++;
46           }

47        }

48        printf("%d\n",ans*2);
49    }

50    return 0;
51}

52

posted on 2011-01-26 00:58 yzhw 阅读(235) 评论(0)  编辑 收藏 引用 所属分类: others


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年10月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜