POJ 1088 滑雪
2021/4/30 18:26:58
本文主要是介绍POJ 1088 滑雪,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
给定一个二维矩阵, 求该矩阵中的最长下降子序列, 该序列的路径可以是上下左右四个方向.
思路分析
记忆化搜索. 先通过dfs遍历4个方向的最长下降子序列, 然后通过记录遍历过的值进行剪枝, 因为dfs过程中会出现重复遍历的情况.
dp[i][j]
表示以矩阵中坐标为(i,j)
的元素为起点的最长下降子序列, dfs的过程中如果遍历到已经处理过的点(i,j)
(即dp[i][j] != 0
)则直接返回当前dp[i][j]
的值, 从而避免重复遍历.
Code
#include <cstdio> #include <cstring> const int maxn = 105; int r, c; int mat[maxn][maxn]; int dp[maxn][maxn]; int ans = 0; int getMax(int a, int b) { return a > b ? a : b; } int dfs(int x, int y) { int tmp = 1; if (dp[x][y] != 0) { return dp[x][y]; } if (x - 1 >= 0 && mat[x - 1][y] < mat[x][y]) { tmp = getMax(dfs(x - 1, y) + 1, tmp); } if (x + 1 < r && mat[x + 1][y] < mat[x][y]) { tmp = getMax(dfs(x + 1, y) + 1, tmp); } if (y - 1 >= 0 && mat[x][y - 1] < mat[x][y]) { tmp = getMax(dfs(x, y - 1) + 1, tmp); } if (y + 1 < c && mat[x][y + 1] < mat[x][y]) { tmp = getMax(dfs(x, y + 1) + 1, tmp); } dp[x][y] = tmp; return tmp; } int main() { scanf("%d%d", &r, &c); memset(dp, 0, sizeof(dp)); for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { scanf("%d", &mat[i][j]); } } for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { ans = getMax(ans, dfs(i, j)); } } printf("%d\n", ans); return 0; }
这篇关于POJ 1088 滑雪的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行