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更长。事实上，这是最长的一条。

      试了各种做法，一开始顺推dp，MLE+TLE各一次。暴力可以几十ms水过。最高效的做法自然是自顶向下记忆化。

 1#include<cstdio>
 2#include<cstdlib>
 3#include<cstring>
 4#define NN 101
 5#define MAX(a,b) (a>b)?a:b
 6int dp[NN][NN];
 7int hArr[NN][NN];
 8int dir[][2]={ {0,1},{0,-1},{1,0},{-1,0} };
 9int n,m;
10
11int dfs(int u,int v){
12    int r,l;
13    if( 0 == dp[u][v] ){
14        for(int k=0;k<4;k++){
15            r=u+dir[k][0];
16            l=v+dir[k][1];
17            if( r>=0&&r<n&&l>=0&&l<m && hArr[r][l]<hArr[u][v] )
18                dp[u][v]=MAX(dp[u][v],dfs(r,l));
19        }
20        ++dp[u][v];
21    }
22    return dp[u][v];
23}
24
25int main(){
26    int res;
27    int i,j;
28    while(scanf("%d%d",&n,&m)!=EOF){
29        for(i=0;i<n;i++) for(j=0;j<m;j++) scanf("%d",&hArr[i][j]);
30        memset(dp,0,sizeof(dp));
31        for(res=i=0;i<n;i++)
32            for(j=0;j<m;j++)
33                res=MAX(res,dfs(i,j));
34        printf("%d\n",res);
35    }
36    return 0;
37}


   最后这道题目让我想起了广东省赛时导致我没得铜牌的那道记忆化，当时死都找不到思路，如今相比之下，不得不感叹自己变化了许多…… 等待越来越近的复仇。