滑雪

题意：给出矩阵地图，值为高度，找一条最长的高度递减的路径。
题解：动态记忆递归搜索，在递归最底层求出最优解，记录，自底向上的方式求出最优解。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cstdio>
 5 using namespace std;
 6 int map[102][102],cnt[102][102];
 7 int sum,temp,n,m;
 8 int DFS(int x,int y){
 9       int max1=0;
10        if(cnt[x][y]>0){
11              return cnt[x][y];
12              }
13     if(x>1&&map[x-1][y]<map[x][y]){
14       max1=max(max1,DFS(x-1,y));
15     }
16     if(x<n&&map[x+1][y]<map[x][y]){
17         max1=max(max1,DFS(x+1,y));
18     }
19     if(y>1&&map[x][y-1]<map[x][y]){
20     max1=max(max1,DFS(x,y-1));
21     }
22     if(y<m&&map[x][y+1]<map[x][y]){
23     max1=max(max1,DFS(x,y+1));
24     }
25     return cnt[x][y]=max1+1;
26 }
27 int main(){
28        scanf("%d%d",&n,&m);
29          memset(cnt,0,sizeof(cnt));
30     for(int i=1;i<=n;i++)
31       for(int j=1;j<=m;j++)
32          scanf("%d",&map[i][j]);
33        sum=0;
34     for(int i=1;i<=n;i++)
35        for(int j=1;j<=m;j++){
36               cnt[i][j]=DFS(i,j);
37                temp=cnt[i][j];
38                if(temp>sum)
39                  sum=temp;
40         }    
41     printf("%d
",sum);     
42 }

View Code