1280:【例9.24】滑雪

2023-12-20 17:43:41

【解题思路】
1. 状态定义
状态定义:dp[i][j]:从(i,j)出发的所有路线中,长度最长的路线的长度。

2. 状态转移方程
记第(i,j)位置的高度为a[i][j]
集合:从(i,j)出发的所有路线
分割集合:根据下一步可以到达的位置分割集合。
下一步可以到达的位置有:(i-1,j), (i+1,j), (i,j-1), (i,j+1)。只要该位置的高度低于当前(i,j)位置的高度,就可以到达这里。

如果a[i-1][j] < a[i][j],那么下一步可以到(i-1,j)。从(i,j)出发的最长路线长度,为从(i-1,j)出发的最长路线长度再加1,即dp[i][j] = dp[i-1][j] + 1
如果a[i+1][j] < a[i][j],那么下一步可以到(i+1,j)。从(i,j)出发的最长路线长度,为从(i+1,j)出发的最长路线长度再加1,即dp[i][j] = dp[i+1][j] + 1
如果a[i][j-1] < a[i][j],那么下一步可以到(i,j-1)。从(i,j)出发的最长路线长度,为从(i,j-1)出发的最长路线长度再加1,即dp[i][j] = dp[i][j-1] + 1
如果a[i][j+1] < a[i][j],那么下一步可以到(i,j+1)。从(i,j)出发的最长路线长度,为从(i,j+1)出发的最长路线长度再加1,即dp[i][j] = dp[i][j+1] + 1
以上四种情况求最大值。
由于在求(i,j)时,其上下左右四个位置的状态:dp[i-1][j], dp[i+1][j], dp[i][j-1], dp[i][j+1]并不能确定都已经求出来了。因此可以通过记忆化递归的方法来求解状态。
设函数dfs(i, j),作用为求解状态dp[i][j]。如果dp[i][j]已经求出来了(值大于0),那么直接返回dp[i][j]。否则通过上述状态转移方程递归求解。

遍历所有的位置,求出从每个位置出发的路线的最长长度,求它们中的最大值,即为该问题的结果。

【题解代码】

#include <iostream>
 
using namespace std;
 
const int N = 105;
 
int n, m, a[N][N], dp[N][N];
int mov[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
 
bool ok(int x, int y) {
	return x > 0 && x <= n && y > 0 && y <= m;
}
 
int dfs(int x, int y) { //返回从起点开始最多能滑几步(不包含起点)
	if (dp[x][y] != 0)
		return dp[x][y];
 
	int maxn = 0;
	for (int i = 0; i < 4; i ++) {
		int dx = x + mov[i][0];
		int dy = y + mov[i][1];
 
		if (ok(dx, dy) && a[dx][dy] < a[x][y]) {
			maxn = max(maxn, dfs(dx, dy));
		}
	}
 
	return dp[x][y] = maxn + 1;
}
 
int main() {
	scanf ("%d %d", &n, &m);
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			scanf ("%d", &a[i][j]);
 
	int ans = 0;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			ans = max(ans, dfs(i, j));
 
	printf ("%d", ans);
	return 0;
}


?

文章来源:https://blog.csdn.net/pheatonhb/article/details/135111157
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。