题解 P1434 【滑雪】

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;//头文件不说啥
int dis[100][100];
int cnt[100][100];
int row,col;//行列数
inline int DP(int i, int j)//状态转移
{
     int max1=0;
    
    if(cnt[i][j]>0)
        return cnt[i][j];//记忆化，如果被搜过，跳就好
    
    //判断dis[i][j-1]是否合法
    if(j-1>=0)//边界条件
      if(dis[i][j]>dis[i][j-1])//转移条件
        if(max1<DP(i,j-1))
          max1=DP(i,j-1);
    
    //判断dis[i][j+1]是否合法
    if(j+1<=col-1)
      if(dis[i][j]>dis[i][j+1])
        if(max1<DP(i,j+1))
            max1=DP(i,j+1);
    
    //判断dis[i-1][j]是否合法
     if(i-1>=0)
        if(dis[i][j]>dis[i-1][j])
        if(max1<DP(i-1,j))
          max1=DP(i-1,j);
    
    //判断dis[i+1][j]是否合法
    if(i+1<=row-1)
      if(dis[i][j]>dis[i+1][j])
        if(max1<DP(i+1,j))
          max1=DP(i+1,j);
 
    return cnt[i][j]=max1+1;//转移
}
int main()
{
    scanf("%d%d",&row,&col);//输入
     for(int i=0;i<=row-1;i++)
        for(int j=0;j<=col-1;j++)
          scanf("%d",&dis[i][j]);

    for(int i=0;i<=row-1;i++)//状态转移
        for(int j=0;j<=col-1;j++)
        DP(i, j);
        
    for(int i=0;i<=row-1;i++)//找最大值
        for(int j=0;j<=col-1;j++)
         if(cnt[0][0]<cnt[i][j])
            cnt[0][0]=cnt[i][j];

    printf("%d",cnt[0][0]);//输出
    return 0;//程序拜拜
}