题意分析

题目给出一个 $R \times C$ 的二维矩阵，每个点代表一个高度。一个人可以从某个点滑向上下左右相邻的四个点之一，当且仅当目标点的高度比当前点低。要求找出最长的滑雪路径的长度。

关键点：

1. 移动规则：只能向相邻的四个方向移动，且高度必须严格递减。
2. 最长路径：需要找到从任意点出发的最长递减路径的长度。

解题思路

这个问题可以转化为在有向无环图（DAG）中寻找最长路径的问题，其中每个点只能指向高度更低的相邻点。由于移动方向只能是高度递减的，所以图中不存在环，可以使用动态规划或记忆化搜索来高效解决。

方法选择：记忆化搜索（DFS + 记忆化）

1. 状态定义：设 $maxLen[i][j]$ 表示从点 $(i, j)$ 出发的最长滑雪路径的长度。
2. 状态转移：
   • 对于点 $(i, j)$，遍历其四个相邻的点 $(x', y')$。
   • 如果 $(x', y')$ 的高度比 $(i, j)$ 低，则 $maxLen[i][j] = \max(maxLen[i][j], maxLen[x'][y'] + 1)$。
3. 初始化：所有点的 $maxLen[i][j]$ 初始值为 1（路径至少包含自己）。
4. 计算顺序：使用深度优先搜索（DFS）递归计算每个点的 $maxLen[i][j]$，并利用记忆化存储避免重复计算。

数学表达

• 状态转移方程：

$$ maxLen[i][j] = 1 + \max_{\text{相邻点 } (x', y') \text{ 满足 }high[x'][y'] < high[i][j]} maxLen[x'][y'] $$

• 最终结果为所有 $maxLen[i][j]$ 的最大值。

解决代码

#include<bits/stdc++.h>
using namespace std;
int to[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int n, m;
int high[105][105];
int maxLen[105][105];
bool check(int x, int y){
	if(x >= 1 && y >= 1 && x <= n && y <= m)
		return 1;
	else
		return 0;
}
 
int dfs(int x, int y){
	if (maxLen[x][y] != 0)	
		return maxLen[x][y];
	
	maxLen[x][y] = 1;       
	for(int i = 0; i <= 4; i++){    
		int x1 = x + to[i][0];
		int y1 = y + to[i][1];
		if( check(x1, y1) && high[x1][y1] < high[x][y]){    
			maxLen[x][y] = max(dfs(x1, y1) + 1, maxLen[x][y]);
		}
	}
	return maxLen[x][y];   
}
int main(){
 
	cin >> n >> m;
 
	int ans = 1;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> high[i][j];
			maxLen[i][j] = 0;      
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			ans = max(ans, dfs(i, j));	
		}
	}
	cout << ans << endl;
	return 0;
} 

代码解释

1. 输入处理：读取矩阵的行数 $R$ 和列数 $C$，以及每个点的高度。
2. 记忆化搜索：
   • dfs(x, y) 函数递归计算从点 $(x, y)$ 出发的最长路径长度，并存储结果以避免重复计算。
   • 遍历四个相邻点，如果高度更低，则递归计算并更新当前点的最长路径长度。
3. 结果计算：遍历所有点，调用 dfs 函数，并记录最大值作为答案。
4. 输出结果：打印最长滑雪路径的长度。