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}


   最后這道題目讓我想起了廣東省賽時導致我沒得銅牌的那道記憶化，當時死都找不到思路，如今相比之下，不得不感嘆自己變化了許多…… 等待越來越近的復仇。