【题目描述】

　　　　滑坡的长度由滑过点的个数来计算，区域由一个二维数组给出，数组的每个数字代表点的高度。下面是一个例子：

　　　　　　　　　　　　　　　　　　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

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

【题目链接】

　　　　http://ybt.ssoier.cn:8088/problem_show.php?pid=1280

【算法】

　　　　记忆化搜索避免排序。

【代码】

1 #include 
     
       2 using namespace std; 3 int r,c,i,j,ans; 4 int dp[110][110],a[110][110]; 5 const int dx[]={-1,0,1,0},dy[]={
   0,1,0,-1}; 6 int solve(int x,int y) 7 { 8     if(dp[x][y]) return dp[x][y]; 9     int ret=1;10     for(int k=0;k<4;k++) {11         int nx=x+dx[k],ny=y+dy[k];12         if(nx>0&&nx<=r&&ny>0&&ny<=c&&a[nx][ny]>a[x][y])13             ret=max(ret,solve(nx,ny)+1);14     }15     dp[x][y]=ret;16     return ret;17 }18 int main()19 {20     scanf("%d%d",&r,&c);21     for(i=1;i<=r;i++)22         for(j=1;j<=c;j++)23             scanf("%d",&a[i][j]);24     for(i=1;i<=r;i++)25     for(j=1;j<=c;j++) {26         if(!dp[i][j]) solve(i,j);27         ans=max(ans,dp[i][j]);28     }29     printf("%d\n",ans);30     return 0;31 }