算法基础之滑雪

滑雪

• 核心思想：记忆化搜索

  • 状态表示： f[i][j] 表示所有从(i,j) 开始滑的路径的最大值

  • 状态计算： 分成四个方向 f[i][j] = max(f[i][j] , f[i][j+1] + 1)

    • 且h[a][b] (下一个点) 必须严格小于 h[i][j] 才能滑过去

  • 

  •   #include<iostream>
      #include<cstring>
      #include<algorithm>
      
      using namespace std;
      const int N = 310;
      
      int f[N][N];
      int h[N][N];
      int n,m;
      int dx[4] = {1,0,-1,0} , dy[4] = {0,1,0,-1};  //四个方向
      
      int dp(int x,int y)
      {
          //记忆化搜索的核心 之前操作求得的f为最大距离 全部保留 下一次直接用即可
          if(f[x][y] != -1) return f[x][y];  //初始化为-1 若滑过 则返回
          
          f[x][y] = 1;  //该点没滑过 初始化为1 只走过这一个点
          for(int i=0;i<4;i++)
          {
              int a = x + dx[i] , b = y + dy[i];
              if(a >=1 && a<=n && b >= 1 && b <= m && h[a][b] < h[x][y])
                  f[x][y] = max(f[x][y] , dp(a,b) + 1);  //递归遍历
          }
          
          return f[x][y];
      }
      
      int main()
      {
          cin>>n>>m;
          
          for(int i=1;i<=n;i++)
              for(int j=1;j<=m;j++)
                  cin>>h[i][j];
                  
          memset(f,-1,sizeof f);  //顺便标记是否滑过
          
          int res = 0;
          for(int i=1;i<=n;i++)
              for(int j=1;j<=m;j++)
                  res = max(res , dp(i,j));  //因为dp函数要有返回值
                  
          cout<<res;
      }