2007年8月23日

 

 1 滑雪 
 2 Time Limit:1000MS  Memory Limit:65536K
 3 Total Submit: 11034  Accepted: 3437  
 4
 5 Description
 6 Michael 喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个 区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 
 7
 8
 9  
10
11 Input
12 输入的第一行表示区域的行数R和列数C( 1   <=  R,C  <=   100 )。下面是R行,每行有C个整数,代表高度h, 0 <= h <= 10000
13
14 Output
15 输出最长区域的长度。
16
17 Sample Input
18
19 5    5
20 1    2    3    4    5
21 16   17   18   19   6
22 15   24   25   20   7
23 14   23   22   21   8
24 13   12   11   10   9
25
26 Sample Output
27 25
28

这道题目非常的好,解题方法也很多,可以用DP,也可以用记忆化搜索,当然还可以暴力破解,不过常规的DP就
足以解决问题了,所以我用了常规的DP来解这道题目
动规方程可以写为path[x][y] = MAX{path[x-1][y], path[x+1][y], path[x][y+1], path[x][y-1]}
如果先按排序再递推的话复杂度会相对小一些


 1 #include < stdio.h >
 2 #include < string .h >
 3 #define  MAX 100
 4
 5 struct  point
 6 {
 7      int  x,y,height;
 8 }
points[MAX * MAX];
 9
10 int  cmp( void   const   * a,  void   const   * b)
11 {   
12      return  ( * ( struct  point * )a).height  -  ( * ( struct  point * )b).height;
13 }
int  path[MAX][MAX];
14
15 int  hills[MAX][MAX];
16 const   int  direction[ 4 ][ 2 =   { 0 , 1 } , { 0 , - 1 } , { 1 , 0 } , { - 1 , 0 } } ;
17
18 int  main()
19 {        
20      int  r, c, i, j, k, ans, x, y;
21     scanf( " %d%d " & r,  & c);
22     k  =   0 ;
23      for  (i  =   0 ; i  <  r;  ++ i)
24          for  (j  =   0 ; j  <  c;  ++ j)
25          {
26             scanf( " %d " & hills[i][j]);
27             points[k].x  =  i;
28             points[k].y  =  j;
29             points[k ++ ].height  =  hills[i][j];
30         }

31         
32         qsort(points, k,  sizeof ( struct  point), cmp);
33
34          for  (i  =   0 ; i < r; i ++ )
35              for  (j  =   0 ; j  < c;j ++ )
36                 path[i][j]  =   0 ;    ans  =   0 ;
37             
38              for  (i = 0 ; i < k;  ++ i)
39              {
40                  for  (j = 0 ;j < 4 ; ++ j)
41                  {
42                     x = points[i].x + direction[j][ 0 ];
43                     y = points[i].y + direction[j][ 1 ];
44                      if  (x >= 0 && x < r && y >= 0 && y < c && hills[x][y] < points[i].height && path[points[i].x][points[i].y] <= path[x][y])
45                         path[points[i].x][points[i].y] = path[x][y] + 1 ;
46                 }

47                  if  (ans <= path[points[i].x][points[i].y])
48                     ans = path[points[i].x][points[i].y];
49             }

50             printf( " %d\n " ,ans + 1 );
51              return   0 ;
52 }


posted @ 2007-08-23 15:30 刘超 阅读(148) | 评论 (0)编辑 收藏

     摘要: Exponentiation  Time  Limit:500MS  Memory Limit:10000KTotal Submit: 22256  Accepted: 5036  DescriptionProblems involving the computation of ...  阅读全文

posted @ 2007-08-23 13:15 刘超 阅读(436) | 评论 (0)编辑 收藏


仅列出标题  

posts - 2, comments - 0, trackbacks - 0, articles - 0

Copyright © 刘超