题解 P1434 【[SHOI2002]滑雪】

· · 题解

我觉得这道题主要方法应该有两种：

  • 动态规划
  • 搜索

下面会分别对这两种方法进行简述

一，动态规划法

首先的想法是用L_{i,j}表示从点(i,j)出发能到达的最长距离。因为从(i,j)出发最少能滑行自己1格，所以每个点L值都先初始化为1

我们可以从(i,j)出发，向四周寻找，如果四周没有比他低的点，那么L_{i,j}即为1，否则L_{i,j}就为从(i,j)出发四周高度比L低且L值最大的那个点P的L值加1

递推时的顺序为点的高度由低到高，那么在递推过程中，计算L_{i,j}时，他四周比他低的点P的L值一定已经被计算出来了

接下来需要解决的问题便是如何按点的高度由小到大递推
关于这个问题，我们难道要每次递推时用两遍循环找出当前未递推的最低点？显然不可取，时间复杂度会爆炸的。那么就考虑能否一个sort()解决问题（懒得自己写排序）。sort()能给一个二维数组排序？不知大佬们怎么想，反正本蒟蒻不会。。。那为了sort()更香可以方便的使用，我用一个一维数组进行存储每个点的数据。

这时候不得不说，结构体真香真的实用。下面用代码直观地说一下这个结构体

struct Point{
    int r;   //行号
    int c;   //列号
    int h;   //高度
    bool operator < (const Point & p) const {
        return h < p.h;
    }//构造函数，不懂的同学可以写一个cmp代替,下面代码会有特别说明
};Point point[10101];

为了方便储存以及不造成浪费（个人习惯）这里i和j都从0开始取，那么点(i,j)用point数组存的下标为c \times i + j

由于i,j从0开始取，c \times i + j这个式子表示的是第i+1行第j+1个数，那么，i最大为R-1，j最大为C-1，整个数组最大下标为C \times (R-1)+C-1，即C \times R-1

若i,j从1开始取，为保证运算方便及善待空间，下标应为C \times (i-1)+j-1

该算法的分析已给出，大家可以结合代码自行理解

#include <iostream>//头文件，不多解释
#include <cstdio>
#include <algorithm>
using namespace std;
struct Point{
    int r;//行号
    int c;//列号
    int h;//高度
    bool operator < (const Point & p) const {
        return h < p.h;//构造函数，不会的可删掉看下面cmp
    }
};Point point[10101];
int cmp(Point a,Point b){
    if (a.h < b.h)   //如果a的高度小于b的高度
      return 1;//返回真
    else
      return 0;//否则返回假
}
int R,C,ans = -0x3ffff;//需初始化ans为较小值（害怕玄学出错）
int a[101][101],d[102][102];//a为每点的高度，d为该点可滑行的最大值
int main(){
    cin >> R >> C;
    for (int i = 0;i < R;i ++)
      for (int j = 0;j < C;j ++){
        cin >> a[i][j];//输入点的高度
        point[i * C + j].h = a[i][j];//根据上面所说的下标，
        point[i * C + j].r = i;      //对点的数据进行存储
        point[i * C + j].c = j;
        d[i][j] = 1;            //初始可滑行长度为1
      }
    sort(point,point + R * C);//如果用了cmp可换为sort(point,point + R * C，cmp);
    for (int i = 0;i < R * C;i ++){
        int r = point[i].r;//找一个替身,怕玄学或运算时出错
        int c = point[i].c;//同理
        if (r > 0 && a[r - 1][c] < a[r][c])//找上面的
          d[r][c] = max(d[r][c],d[r - 1][c] + 1);//进行更新
        if (c > 0 && a[r][c - 1] < a[r][c])//找左面的
          d[r][c] = max(d[r][c],d[r][c - 1] + 1);//进行更新
        if (r < R - 1 && a[r + 1][c] < a[r][c])//找下面的
          d[r][c] = max(d[r][c],d[r + 1][c] + 1);//进行更新
        if (c < C - 1 && a[r][c + 1] < a[r][c])//找右面的
          d[r][c] = max(d[r][c],d[r][c + 1] + 1); //进行更新
    }
    for (int i = 0;i < R;i ++)
      for (int j = 0;j < C;j ++)
        ans = max(ans,d[i][j]); //找出最大值
    cout << ans;
    return 0;//完美撒花

由于点(i,j)的L值的计算为极小的常数值，所以这个算法的复杂度为O(R \times C)

二、搜索

相信大家都会想到DFS，但若是单纯的DFS，会TLE一个点，所以，我们就要考虑到记忆化搜索。那么也很好实现，具体请见下方代码：

#include <iostream>
#include <cstdio>
using namespace std;
int R,C;
int g1[4] = {0,1,0,-1};//定义寻找的4个方向
int g2[4] = {-1,0,1,0};
int m[101][101];//储存每个点的高度
int lj[101][101];//储存每个点可滑行的最大长度
int maxn,lr;
int dfs(int i,int j){
    if (lj[i][j] - 1)//判断是否搜过，因为下面将每一个点的最初滑行长度为1
                 //如果该点最长长度-1为0，说明该点未被搜过
      return lj[i][j];
    for (int o = 0;o < 4;o ++)//向4个方向搜
      if (i + g1[o] >= 0 && i + g1[o] < R && j + g2[o] >= 0 && j + g2[o] < C && m[i + g1[o]][j + g2[o]] < m[i][j]){//保证不越界
        lj[i][j] = max(lj[i][j],dfs(i + g1[o],j + g2[o]) + 1);//进行搜索及更新
      }
    return lj[i][j];
}
int main(){
    cin >> R >> C;
    for (int i = 0;i < R;i ++)//初始化
      for (int j = 0;j < C;j ++)
        lj[i][j] = 1;
    for (int i = 0;i < R;i ++)
      for (int j = 0;j < C;j ++)
        cin >> m[i][j];
    for (int i = 0;i < R;i ++)
      for (int j = 0;j < C;j ++){
        if (lj[i][j] - 1 != 0){//如果该点被搜过
            maxn = max(maxn,lj[i][j]);//直接更新
            continue;
          }
        lj[i][j] = dfs(i,j);
        maxn = max(maxn,lj[i][j]);
      }
    cout << maxn;
    return 0;//撒花
}

这就是该题本人的思路，希望能给你带来帮助