poj 1088

滑雪

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 72231		Accepted: 26652

Description

Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

 1  2  3  4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。

Input

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

Output

输出最长区域的长度。

Sample Input

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

Sample Output

Source

SHTSC 2002

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<queue>
 6 using namespace std;
 7 
 8 int a[101][101];
 9 int dp[101][101];
10 int n,m;
11 int map1[4][2]={ {1,0},{0,1},{-1,0},{0,-1} };
12 
13 
14 int Max(int x,int y)
15 {
16     return x>y? x:y;
17 }
18 int dfs(int x,int y)
19 {
20     int i,x1,y1,cur=0;
21     if(dp[x][y]>0) return dp[x][y];
22 
23     for(i=0;i<4;i++)
24     {
25         x1=x+map1[i][0];
26         y1=y+map1[i][1];
27         if(x1>=1&&x1<=n && y1>=1&&y1<=m)
28         {
29             if(a[x1][y1]<a[x][y])
30                 cur=Max(cur,dfs(x1,y1));
31         }
32     }
33     dp[x][y]=cur+1;
34     return  dp[x][y];
35 }
36 int main()
37 {
38     int i,j,ans;
39     while(scanf("%d%d",&n,&m)>0)
40     {
41         for(i=1;i<=n;i++)
42             for(j=1;j<=m;j++)
43                 scanf("%d",&a[i][j]);
44         memset(dp,0,sizeof(dp));
45         for(i=1;i<=n;i++)
46         {
47             for(j=1;j<=m;j++)
48             {
49                 if(dp[i][j]==0)
50                 {
51                     ans=dfs(i,j);
52                 }
53             }
54         }
55         ans=0;
56         for(i=1;i<=n;i++)
57         {
58             for(j=1;j<=m;j++)
59             {    
60                 if(dp[i][j]>ans)
61                     ans=dp[i][j];
62             }
63         }
64         printf("%d
",ans);
65     }
66     return 0;
67 }

方法二，庆神的方法，为什么他没有过，而我过了(⊙o⊙)…

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 struct node
 9 {
10     int x,y;
11     int val;
12 }f[10002];
13 int dp[101][101],a[101][101],len;
14 int map1[4][2]={{1,0},{0,1},{0,-1},{-1,0} };
15 
16 bool cmp(node n1,node n2)
17 {
18     return n1.val<n2.val;
19 }
20 int Max(int x,int y)
21 {
22     return  x>y? x:y;
23 }
24 int main()
25 {
26     int n,m;
27     int i,j,k,x,y,hxl,x1,y1;
28     while(scanf("%d%d",&n,&m)>0)
29     {
30         len=0;
31         for(i=1;i<=n;i++)
32             for(j=1;j<=m;j++)
33             {
34                 scanf("%d",&f[++len].val);
35                 a[i][j]=f[len].val;
36                 f[len].x=i;
37                 f[len].y=j;
38             }
39         k=n*m;
40         sort(f+1,f+1+k,cmp);
41         memset(dp,0,sizeof(dp));
42         for(i=1;i<=k;i++)
43         {
44             x=f[i].x;
45             y=f[i].y;
46             hxl=0;
47             for(j=0;j<4;j++)
48             {
49                 x1=x+map1[j][0];
50                 y1=y+map1[j][1];
51                 if(x1>=1&&x1<=n && y1>=1&&y1<=m)
52                 {
53                     if(a[x1][y1]<a[x][y])
54                     hxl=Max(hxl,dp[x1][y1]);
55                 }
56             }
57             dp[x][y]=hxl+1;
58         }
59         hxl=-1;
60         for(i=1;i<=n;i++)
61         {
62             for(j=1;j<=m;j++)
63                 if(dp[i][j]>hxl)
64                     hxl=dp[i][j];
65         }    
66         printf("%d
",hxl);
67 
68     }
69     return 0;
70 }