洛谷 P1434 [SHOI2002]滑雪(DP,记忆化搜索)
发布日期:2022-04-01 13:25:20
浏览次数:37
分类:博客文章
本文共 2944 字,大约阅读时间需要 9 分钟。
题目描述
Michael喜欢滑雪。这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子:
1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可行的滑坡为 (从 开始,在 结束)。当然 更长。事实上,这是最长的一条。
输入输出格式
输入格式:
输入的第一行为表示区域的二维数组的行数 和列数 ( , )。下面是 行,每行有 个数,代表高度(两个数字之间用1个空格间隔)。
输出格式:
输出区域中最长滑坡的长度。
输入输出样例
输入样例#1:
5 51 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9
输出样例#1:
25
思路
可以轻易地推出状态转移方程为:
但是 的值不能通过普通的线性dp来求的,所以需要进行记忆化搜索来遍历所有的状态,并进行记忆化,这样就可以获得上述四个状态的值了,然后进行dp即可
也可以将二维的地图进行降维,然后进行线性dp,具体方法请看dalao博客:
AC代码
/************************************************************************* > Author: WZY > School: HPU > Created Time: 2019-02-06 20:45:27 ************************************************************************/#include#define ll long long#define ull unsigned long long#define ms(a,b) memset(a,b,sizeof(a))#define INF 0x7f7f7f7fconst int maxn=1e3+10;const int mod=1e9+7;using namespace std;int a[maxn][maxn];int dp[maxn][maxn];int dir[4][2]={1,0,-1,0,0,1,0,-1};int n,m;int dfs(int x,int y){ if(dp[x][y]) return dp[x][y]; int _=0; for(int i=0;i<4;i++) { int dx=x+dir[i][0]; int dy=y+dir[i][1]; if(dx<=n&&dx>0&&dy<=m&&dy>0&&a[x][y]>a[dx][dy]) _=max(dfs(dx,dy)+1,_); } dp[x][y]=max(_,dp[x][y]); return dp[x][y];}int main(int argc, char const *argv[]){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; ms(dp,0); int ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans=max(ans,dfs(i,j)); cout< <
转载地址:https://www.cnblogs.com/Friends-A/p/11054975.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年04月03日 19时33分00秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Python 基础知识考题与解答(2020 版)
2021-06-29
说说 Oracle 的 SYSDATE 函数
2021-06-29
说说 Oracle 的 NVL 与 NVL2 函数
2021-06-29
说说 TCP 协议以及三次握手流程
2021-06-29
说说 Oracle 的 TRUNC 函数
2021-06-29
系统架构设计笔记(41)—— 系统过渡计划
2021-06-29
系统架构设计笔记(42)—— 软件架构概述
2021-06-29
系统架构设计笔记(57)—— 测试自动化与面向对象的测试
2021-06-29
系统架构设计笔记(58)—— 嵌入式系统概论
2021-06-29
说说 Python 的生成器表达式
2021-06-29
说说 Activiti 中的用户与组的概念
2021-06-29
系统架构设计笔记(62)—— 嵌入式数据库管理系统
2021-06-29
系统架构设计笔记(63)—— 实时嵌入式操作系统
2021-06-29
说说如何使用 Canvas 绘制弧线与曲线
2021-06-29
系统架构设计笔记(64)—— 嵌入式系统设计
2021-06-29
系统架构设计笔记(65)—— 项目的范围、时间与成本
2021-06-29
系统架构设计笔记(66)—— 配置管理与文档管理
2021-06-29
说说 Python 元组的高级用法
2021-06-29
系统架构设计笔记(66)—— 配置管理与文档管理
2021-06-29