当前位置: 首页 > news >正文

记忆化搜索,901. 滑雪

901. 滑雪 - AcWing题库

给定一个 R 行 C 列的矩阵,表示一个矩形网格滑雪场。

矩阵中第 i行第 j 列的点表示滑雪场的第 i 行第 j列区域的高度。

一个人从滑雪场中的某个区域内出发,每次可以向上下左右任意一个方向滑动一个单位距离。

当然,一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

下面给出一个矩阵作为例子:

 1  2  3  4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9

在给定矩阵中,一条可行的滑行轨迹为 24−17−2−1。

在给定矩阵中,最长的滑行轨迹为 25−24−23−…−3−2−1,沿途共经过 25 个区域。

现在给定你一个二维矩阵表示滑雪场各区域的高度,请你找出在该滑雪场中能够完成的最长滑雪轨迹,并输出其长度(可经过最大区域数)。

输入格式

第一行包含两个整数 R 和 C。

接下来 R 行,每行包含 C 个整数,表示完整的二维矩阵。

输出格式

输出一个整数,表示可完成的最长滑雪长度。

数据范围

1≤R,C≤300
0≤矩阵中整数≤10000

输入样例:
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

解析

AcWing 901. 滑雪 - AcWing

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
using namespace std;
typedef long long LL;
const int N = 305;
int n, m;
int h[N][N];
int f[N][N];int ax[] = { 0,0,1,-1 }, ay[] = { 1,-1,0,0 };int dp(int x, int y) {int& v = f[x][y];if (v != -1)return v;v = 1;for (int i = 0; i < 4; i++) {int a = x + ax[i], b = y + ay[i];if (a >= 1 && a <= n && b >= 1 && b <= m && h[x][y] > h[a][b])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]);}memset(f, -1, sizeof(f));int ans = 0;for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)ans = max(ans, dp(i, j));cout << ans << endl;return 0;
}

相关文章:

记忆化搜索,901. 滑雪

901. 滑雪 - AcWing题库 给定一个 R 行 C 列的矩阵&#xff0c;表示一个矩形网格滑雪场。 矩阵中第 i行第 j 列的点表示滑雪场的第 i 行第 j列区域的高度。 一个人从滑雪场中的某个区域内出发&#xff0c;每次可以向上下左右任意一个方向滑动一个单位距离。 当然&#xff0…...

计算机网络:连接世界的纽带

计算机网络的基础概念 计算机网络是一组相互连接的计算机&#xff0c;它们通过通信链路和协议进行数据交换和资源共享。以下是一些关键概念&#xff1a; 1. 节点和主机 网络中的计算机设备称为节点&#xff0c;通常是主机或服务器。主机是普通用户或终端设备&#xff0c;而服…...

SpringMVC 学习(三)注解开发

4. 注解开发 4.1 环境搭建 (1) 新建 maven 模块 springmvc-03-annotation (2) 确认依赖 确认方法同 3(2)&#xff0c;手动导入发布依赖见3(11) <!--资源过滤--> <build><resources><resource><directory>src/main/java</directory>&…...

0x84加密数据传输服务

为了在安全模式下实现一些诊断服务&#xff0c;在服务端和客户端应用程序之间添加了Security sub-layer。在客户端与服务端之间进行诊断服务数据传输有两种方法&#xff1a; 1、非安全模式下数据传输   应用程序使用诊断服务(diagnostic Services)和应用层服务原语(Applicati…...

Vue.js快速入门:构建现代Web应用

Vue Vue.js是一款流行的JavaScript框架&#xff0c;用于构建现代的、交互式的Web应用程序。它具有简单易学的特点&#xff0c;同时也非常强大&#xff0c;能够帮助开发者构建高效、可维护的前端应用。本篇博客将带你快速入门Vue.js&#xff0c;并演示如何构建一个简单的Vue应用…...

Scala第五章节

Scala第五章节 scala总目录 章节目标 掌握方法的格式和用法掌握函数的格式和用法掌握九九乘法表案例 1. 方法 1.1 概述 实际开发中, 我们需要编写大量的逻辑代码, 这就势必会涉及到重复的需求. 例如: 求10和20的最大值, 求11和22的最大值, 像这样的需求, 用来进行比较的逻…...

erlang练习题(三)

题目一 查询列表A是否为列表B的前缀 解答 isPrefix([], List2) -> io:format("A is prefix of B ~n");isPrefix([H1 | ListA], [H2 | ListB]) ->case H1 H2 oftrue -> isPrefix(ListA, ListB);false -> io:format("A is not prefix of B ~n&quo…...

What Is A DNS Amplification DDoS Attack?

什么是 DNS 放大攻击&#xff1f; 域名系统 &#xff08;DNS&#xff09; 是用于在网站的机器可读地址&#xff08;例如 191.168.0.1&#xff1a;80&#xff09;和人类可读名称&#xff08;例如 radware.com&#xff09;之间进行解析的目录在 DNS 放大攻击中&#xff0c;攻击者…...

jvm笔记

好处&#xff1a; 跨平台 内存管理机制&#xff0c;垃圾回收功能 数组下标越界检查 多态 名词解释&#xff1a; jvm java虚拟机&#xff0c;是java程序的运行环境 jre jvm基础类库 jdk jre编译工具 javase jdkide工具 javaee javase应用服务器 jvm的内存结构&#xff1a; 程序…...

WPF中的控件

内容控件&#xff1a;label、border Window控件 Label控件 Border控件 内容控件 Button控件 点击取消按钮关闭程序&#xff1b;点击登录按钮打开BorderWindow窗口。 TextBox控件 PasswordBox控件 TextBlock控件 加载窗口时显示TextBlock中的内容 RadioButton控件 CheckBox控件…...

Java下对象的序列化和反序列化(写出和读入)

代码如下&#xff1a; public class MyWork {public static void main(String[] args) throws IOException, ClassNotFoundException {//序列化File f new File("testFile/testObject.txt");ObjectOutputStream oos new ObjectOutputStream(new FileOutputStream(…...

基于springboot的洗衣店订单管理系统

目录 前言 一、技术栈 二、系统功能介绍 顾客信息管理 店家信息管理 店铺信息管理 洗衣信息管理 预约功能 洗衣信息 交流区 三、核心代码 1、登录模块 2、文件上传模块 3、代码封装 前言 随着信息互联网信息的飞速发展&#xff0c;无纸化作业变成了一种趋势&#x…...

Llama2部署踩坑

1、权重是.bin&#xff0c;但是报错找不到.safetensors 明明权重文件是.bin&#xff0c;但是却提示我缺少.safetensors。最后发现好像是 llama2-7b这个模型文件不行&#xff0c;必须要llama2-7b-chat这个模型才能读取的通&#xff0c;具体原因还暂不明确。...

Adams齿轮副

1.运动副 添加旋转副的时候&#xff0c;必须先物体后公共part(即此处的ground&#xff09;&#xff0c;最后再选择质心点 2.啮合点 啮合点marker的z轴必须是齿轮分度圆的切线方向 3.啮合点 两齿轮的旋转副&#xff0c;和啮合点&#xff0c;即cv marker &#xff0c;必须属…...

Elasticsearch keyword 中的 ignore_above配置项

1. ignore_above 关于es mapping的keyword ignore_above配置项的解释如下&#xff1a; Do not index any string longer than this value. Defaults to 2147483647 so that all values would be accepted. 不会索引大于ignore_above配置值的数据&#xff0c;默认值2147483647字…...

RabbitMQ原理(一):基础知识

文章目录 1.初识MQ1.1.同步调用1.2.异步调用1.3.技术选型2.RabbitMQ2.1.安装2.2.收发消息2.2.1.交换机2.2.2.队列2.2.3.绑定关系2.2.4.发送消息2.3.数据隔离2.3.1.用户管理2.3.2.virtual host微服务一旦拆分,必然涉及到服务之间的相互调用,目前我们服务之间调用采用的都是基于…...

[Linux]Git

文章摘于GitHub博主geeeeeeeeek 文章目录 1.1 Git 简易指南创建新仓库工作流添加与提交推送改动 1.2 创建代码仓库git init用法讨论裸仓库 例子 git clone用法讨论仓库间协作 例子用法讨论栗子 1.3 保存你的更改git add用法讨论缓存区 栗子 git commit用法讨论记录快照&#xf…...

ChatGPT终于可以进行网络搜索 内容不再限于2021年9月前

微软和谷歌已经让旗下聊天机器人进行网上搜索&#xff0c;并提供原始材料的链接&#xff0c;以提高信息共享的可信度和范围。但是&#xff0c;ChatGPT迄今为止只接受了有时间限制的训练数据&#xff0c;这些数据仅限于从互联网上收集的2021年9月之前的信息。在周三的一系列推文…...

uni-app:实现页面效果1

效果 代码 <template><view><view class"add"><image :src"add_icon" mode""></image></view><view class"container_position"><view class"container_info"><view c…...

归一化和标准化的联系与区别及建议

归一化和标准化是数据预处理中常用的两种方法。它们都是为了调整数据的尺度,使得数据更符合我们的分析需求。虽然二者的目的相同但是具体实现方式和适用场景却有所不同。下面,我们来详细介绍-下它们的联系和区别。 一、联系 归一化和标准化都能够使得数据的尽度缩放到不同的…...

数据结构--栈的实现

数据结构–栈的实现 1.栈的概念和结构&#xff1a; 栈的概念&#xff1a;栈是一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO&#xff08;Las…...

第十章 异常

python使用异常的特殊对象管理程序执行期间发生的错误。每当发生错误时&#xff0c;python会创建异常对象。如果编写了处理该异常的代码&#xff0c;程序将继续运行&#xff1b;如果未处理&#xff0c;程序将显示traceback。 异常是使用try-except代码块处理的。使用try-excep…...

Rust冒泡排序

Rust冒泡排序 这段代码定义了一个名为 bubble_sort 的函数&#xff0c;接受一个可变的整数类型数组作为输入&#xff0c;然后使用嵌套的循环来实现冒泡排序。外部循环从数组的第一个元素开始迭代到倒数第二个元素&#xff0c;内部循环从数组的第一个元素开始迭代到倒数第二个元…...

麒麟信安服务器操作系统V3.5.2重磅发布!

9月25日&#xff0c;麒麟信安基于openEuler 22.03 LTS SP1版本的商业发行版——麒麟信安服务器操作系统V3.5.2正式发布。 麒麟信安服务器操作系统V3定位于电力、金融、政务、能源、国防、工业等领域信息系统建设&#xff0c;以安全、稳定、高效为突破点&#xff0c;满足重要行…...

密码技术 (1) - 对称密码

一. 前言 对称密码是指加密数据和解密数据使用的是相同的秘钥。发送者使用秘钥将加密后的数据发送给接受者&#xff0c;接收者收到数据后用相同的秘钥解密&#xff0c;恢复原始数据。 对称密码具有加密和解密快速的特点&#xff0c;适用于需要快速加密的场景&#xff0c;常用的…...

基于PYQT5的GUI开发系列教程【二】QT五个布局的介绍与运用

目录 本文概述 作者介绍 创建主窗口 水平布局 垂直布局 栅格布局 分裂器水平布局 分裂器垂直布局 自由布局 取消原先控件的布局的方法 尾言 本文概述 PYQT5是一个基于python的可视化GUI开发框架&#xff0c;具有容易上手&#xff0c;界面美观&#xff0c;多平台…...

Cadence PCB 焊盘和封装

封装(Packaging) 封装指的是在电子元件制造中将电子元件(例如集成电路芯片、电子元器件等)进行物理保护和连接的过程。封装通常涉及将电子元件封装到外部保护壳或包装中,以确保其正常运作、连接到电路板并保护它们免受环境因素的影响。 封装的主要目标包括以下几个方面:…...

正在等待操作系统重新启动。 请重新启动计算机以安装autocad 2024。

正在等待操作系统重新启动。 请重新启动计算机以安装autocad 2024。 这是刚启动Autodesk 2024产品就弹出的弹窗&#xff0c;重启之后启动还是有这个 一直阻止安装程序运行 出现问题的原因是安装包存在问题 使用正确的安装包即可解决这个问题 需要的朋友查看图片或者评伦取…...

Windows电脑显示部分功能被组织控制

目录 问题描述 解决方法 总结 问题描述 如果你的电脑出现以上情况&#xff0c;建议你使用我这种方法&#xff08;万不得已&#xff09; 解决方法 原因就是因为当时你的电脑在激活的时候是选择了组织性激活的&#xff0c;所以才会不管怎么搞&#xff0c;都无法摆脱组织的控…...

Django模板加载与响应

前言 Django 的模板系统将 Python 代码与 HTML 代码解耦&#xff0c;动态地生成 HTML 页面。Django 项目可以配置一个或多个模板引擎&#xff0c;但是通常使用 Django 的模板系统时&#xff0c;应该首先考虑其内置的后端 DTL&#xff08;Django Template Language&#xff0c;D…...

网站psd切图做响应式效果/惠州seo外包平台

原文地址为&#xff1a; 征服ExtJs那棵树(ExtJs官方开发手册汉语详解--TreePanel)结构图 概述 TreePanel是在Ext JS中最功能丰富的组件之一&#xff0c;是一个非常棒的工具&#xff0c;用于显示在应用程序中的结构化数据。TreePanel是从GridPane继承的类,因此,所有GridPanel的特…...

国内谷歌网站SEO优化/seo收索引擎优化

RxJava正在Android开发者中变的越来越流行。唯一的问题就是上手不容易&#xff0c;尤其是大部分人之前都是使用命令式编程语言。但是一旦你弄明白了&#xff0c;你就会发现RxJava真是太棒了。 这里仅仅是帮助你了解RxJava&#xff0c;整个系列共有四篇文章&#xff0c;希望你看…...

南昌制作网站的公司吗/网站推广营销

文章目录 一、题目🔸题目描述🔸输入输出🔸样例1二、代码参考作者:KJ.JK🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🍂个人博客首页: KJ.JK 💖系列专栏:华为OD机试(Java&Python&C语言) 一、题目 🔸题目描述 对输入的字符串进…...

怎样做网站底部导航/杭州seo公司

$(window).bind("load", function () {  var height $(document.body).height();$(.syntaxhighlighter).height(height); });转载于:https://www.cnblogs.com/bushe/p/5241642.html...

山东搜点网站建设/友情链接交换

问题描述 在某个线上网站&#xff0c;电商网站&#xff0c;当进入确定订单页面&#xff0c;填写买家留言以后&#xff0c;页面跳转到订单支付页面&#xff0c;下面的fixed定位的支付按钮就会消失&#xff0c;该问题烦恼了很久&#xff0c;于是。。 百度之&#xff1a; 这几天…...

室内装修设计上海/深圳知名seo公司

二值化核心思想 设阈值&#xff0c;大于阈值的为0&#xff08;黑&#xff09;或255&#xff08;白&#xff09;&#xff0c;使图像成为黑白图。 阈值可固定&#xff0c;也可自适应阈值。 自适应阈值一般为一点像素与这点为中心的区域像素平均值或者高斯分布加权和的比较&#x…...