AcWing 901. 滑雪
题目
题目描述
给定一个 行 列的矩阵 ，表示一个矩形网格滑雪场。
矩阵中第 行第 列的点表示滑雪场的第 行第 列区域的高度。
一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。
当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。
下面给出一个矩阵作为例子：
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在给定矩阵中，一条可行的滑行轨迹为 。
在给定矩阵中，最长的滑行轨迹为 ，沿途共经过 个区域。
现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。
输入格式
第一行包含两个整数 和 。
接下来 行，每行包含 个整数，表示完整的二维矩阵。
输出格式
输出一个整数，表示可完成的最长滑雪长度。
数据范围
,
输入样例：
5 5
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输出样例：
25思路
状态表示f[i, j]
-
集合：所有从
(i, j)开始滑的路径 -
属性：
max
状态计算：假设f[i, j]可以表示所有方案。可以按照第一步往哪个方向滑，分成四种情况。
这四种情况应该是不重不漏的，每条路径属于且只属于其中的一类。那么f[i][j]的值应该是下面四种的最大值再取max。
上：f[i][j] -> f[i - 1][j] -> ... -> 终点。
下：f[i][j] -> f[i + 1][j] -> ... -> 终点。
左：f[i][j] -> f[i][j - 1] -> ... -> 终点。
右：f[i][j] -> f[i][j + 1] -> ... -> 终点。
因为f[i][j]是相同的，可以先减去它，这样不影响最大值是谁。变成：
上：f[i - 1][j] -> ... -> 终点。
下：f[i + 1][j] -> ... -> 终点。
左：f[i][j - 1] -> ... -> 终点。
右：f[i][j + 1] -> ... -> 终点。
当然，对于f[i][j]并不是每类都存在。存在的前提条件是，滑向点的高度要小于当前点的高度。所以只需要把存在的情况都枚举一遍，再取max就可以了。
dp问题能做的前提，前提条件是遍历的图必须是一个拓扑图，即相互之间的依赖不存环。
比如算f[i][j]的时候用到了f[i][j - 1]，算f[i][j - 1]又用到了状态B，而状态B又依赖f[i][j]。这样的话，我们每一个值都求不出来。
这个题是不存在环的，因为a > b > c > ... > a，可以推出a > a，因为是严格递减的，所有这是不可能的。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 310;
int n, m;
int h[N][N]; // 高度
int f[N][N]; // dp的状态
int dx[4] = {-1, 1, 0, 0}, dy[4]= {0, 0, -1, 1};
// 求出从x，y这个点出发的最大值并且返回
int dp(int x, int y)
{
int &v = f[x][y];
// v已经算过了
if ( v != -1 ) return v;
v = 1; // 即不能再往下滑，但这个点初始值应该是1。
// 枚举从x，y出去的四个方向
for ( int i = 0; i < 4; i ++ )
{
int a = dx[i] + x, b = dy[i] + y;
// 在界限内，且可以滑下去
if ( a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y] )
v = max(v, dp(a, b) + 1); // 走过去，加上这个点
}
return v;
}
int main()
{
scanf("%d%d", &n, &m);
for ( int i = 1; i <= n; i ++ )
for ( int j = 1; j <= m; j ++ )
scanf("%d", &h[i][j]);
// 递归的去算每个状态，将每个状态初始化成-1，表示每个状态没有被算过
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));
printf("%d\n", res);
return 0;
}