——以“[SHOI2002] 滑雪”为例
题目描述
Michael 喜欢滑雪。这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子：
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
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度会减小。在上面的例子中，一条可行的滑坡为 \(24－17－16－1\)（从 \(24\) 开始，在 \(1\) 结束）。当然 \(25－24－23－…－3－2－1\) 更长。事实上，这是最长的一条。
输入格式
输入的第一行为表示区域的二维数组的行数 \(R\) 和列数 \(C\)。下面是 \(R\) 行，每行有 \(C\) 个数，代表高度(两个数字之间用 \(1\) 个空格间隔)。
输出格式
输出区域中最长滑坡的长度。
题目分析
一开始，本蒟蒻看到是个最短路问题，飞快的打了个BFS代码出来，后来TLE了一个次测试点，一想，如果一个高度已经在一次滑的过程当中被划过了自然不可能作为另一次滑的起点，于是加入一个vis数组尝试去重。结果依旧TLE了一个点。
这就遇到本蒟蒻的知识盲区了呀
查阅相关资料可知，这一题可以使用记忆化搜索过，二话不说，整一个记忆化出来。也以此为契机，浅析一下记忆化搜索
我们以为例
4 4 1 2 3 6 2 4 4 3 2 5 4 2 1 3 4 7
模拟一下搜索的过程
\((1,1)\) 只有一个点，不能继续滑，就是 \(1\)， \((1,2)\) 呢，可以从 \((1,2)\) 滑到 \((1,1)\) 距离就是 \(2\) 。
如果不加以任何优化的话，我们就要一直遍历到最后一个 \((4,4)\) 才能肯定最长距离是 \(4\) 。这显然不够理想，或者说，我们中间浪费搜索了非常多的阶段，比如说从 \((1,2)\) 到 \((1,1)\) 这个两步我们在之后的搜索当中反复的遇到，而这是完全可以得到优化的。
我们已知从 \((i,j)\) 向下滑的最长距离是一定的，那也就是说 \((i,j)\) 处的结果是确定的，之后的搜索如果搜索到了 \((i,j)\) 就可以直接在现有的长度上加上 \((i,j)\) 所对应的能够滑到最底的结果就可以了。
我们都知道，深搜是一个从叶子节点向根节点回溯的过程，也就是说在回溯到 \((i,j)\) 节点处时，周围的节点都已经得到了最终的更新，那么我们维护 \((i,j)\) 处的值，可知 \((i,j)\) 的最长距离应该等于周围四个节点值的最大值+1。
代码如下
Accepted Code
/*
* @Author: Gehrychiang
* @Date: 2020-02-05 22:42:23
* @Website: www.yilantingfeng.site
* @E-mail: gehrychiang@aliyun.com
*/
#include <bits/stdc++.h>
using namespace std;
int n, m;
int res = 0; //最终结果
int field[105][105];
int ans[105][105]; //记忆
void dfs(int curx, int cury)
{
if (ans[curx][cury] != 0)
{
return;
}
ans[curx][cury] = 1; //根据题意自己也算一个距离
int curh = field[curx][cury]; //常数优化
if (curx - 1 >= 1 && field[curx - 1][cury] < curh)
{
dfs(curx - 1, cury);//向下搜索
ans[curx][cury] = max(ans[curx - 1][cury] + 1, ans[curx][cury]);//一旦回溯至此即根据周围节点更新自身
}
if (curx + 1 <= n && field[curx + 1][cury] < curh)
{
dfs(curx + 1, cury);
ans[curx][cury] = max(ans[curx + 1][cury] + 1, ans[curx][cury]);
}
if (cury - 1 >= 1 && field[curx][cury - 1] < curh)
{
dfs(curx, cury - 1);
ans[curx][cury] = max(ans[curx][cury - 1] + 1, ans[curx][cury]);
}
if (cury + 1 <= m && field[curx][cury + 1] < curh)
{
dfs(curx, cury + 1);
ans[curx][cury] = max(ans[curx][cury + 1] + 1, ans[curx][cury]);
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> field[i][j];
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
dfs(i, j);
res = max(res, ans[i][j]);
}
}
cout << res << endl;
return 0;
}