动态规划DP 数字三角型模型 最低通行费用(题目详解+C++代码完整实现)
最低通行费用
原题链接
AcWing 1018. 最低同行费用
题目描述
一个商人穿过一个 N×N的正方形的网格,去参加一个非常重要的商务活动。
他要从网格的左上角进,右下角出。每穿越中间 1个小方格,都要花费 1个单位时间。商人必须在 (2N−1)个单位时间穿越出去。
而在经过中间的每个小方格时,都需要缴纳一定的费用。
这个商人期望在规定时间内用最少费用穿越出去。
请问至少需要多少费用?
注意:不能对角穿越各个小方格(即,只能向上下左右四个方向移动且不能离开网格)。
输入格式
第一行是一个整数,表示正方形的宽度 N。后面 N行,每行 N个不大于 100的正整数,为网格上每个小方格的费用。
输出格式
输出一个整数,表示至少需要的费用。
数据范围
1≤N≤100
输入样例:
5
1 4 6 8 10
2 5 7 15 17
6 8 9 18 20
10 11 12 19 21
20 23 25 29 33
输出样例:
109
样例解释
样例中,最小值为 109=1+2+5+7+9+12+19+21+33。
题目分析
“商人必须在 (2N−1)个单位时间穿越出去” 意味着不能走回头路,
因此,该题转化为 “ 摘花生 ”。
不同点在于,该题 “最低通行费” 所求为最小值(min),而 “摘花生” 所求为最大值(max)。
全局变量的初值默认为0,最小值(min)在求解过程中可能涉及到初始化问题,因为0可以是最小值,而边界情况又是不合理的,需要我们多加处理。
数据的初始化处理
第一列 (i,1):
路径不可能来自第一列的左侧,f[i][0] 初始化为INF。
第一行(1,j):
路径不可能来自第一行的上侧,f[0][j] 初始化为INF。
同时,在状态计算的过程当中,路径一定过起点(1,1),因此,f[1][1]的状态值不由f[0][1]或者f[1][0]得到,而是直接赋值为 w[1][1]。
完整代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=110;
const int INF=2e9;
int n;
int w[N][N]; //费用
int f[N][N]; //状态表示
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&w[i][j]);}}//初始化处理for(int i=1;i<=n;i++){f[i][0]=INF; //第一列的左侧f[0][i]=INF; //第一行的上侧}//状态计算for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i==1&&j==1) f[1][1]=w[1][1]; //如果是起始点(1,1),则直接赋值w[1][1]else f[i][j]=min(f[i-1][j],f[i][j-1])+w[i][j]; //否则通过状态计算}}printf("%d",f[n][n]); //右下角终点(n,n)的f状态值即为最终答案return 0;
}
相关文章:
动态规划DP 数字三角型模型 最低通行费用(题目详解+C++代码完整实现)
最低通行费用 原题链接 AcWing 1018. 最低同行费用 题目描述 一个商人穿过一个 NN的正方形的网格,去参加一个非常重要的商务活动。 他要从网格的左上角进,右下角出。每穿越中间 1个小方格,都要花费 1个单位时间。商人必须在 (2N−1)个单位…...
deepseek R1的确不错,特别是深度思考模式
deepseek R1的确不错,特别是深度思考模式,每次都能自我反省改进。比如我让 它写文案: 【赛博朋克版程序员新春密码——2025我们来破局】 亲爱的代码骑士们: 当CtrlS的肌肉记忆遇上抢票插件,当Spring Boot的…...
Linux 常用命令 - sort 【对文件内容进行排序】
简介 sort 命令源于英文单词 “sort”,表示排序。其主要功能是对文本文件中的行进行排序。它可以根据字母、数字、特定字段等不同的标准进行排序。sort 通过逐行读取文件(没有指定文件或指定文件为 - 时读取标准输入)内容,并按照…...
MyBatis最佳实践:提升数据库交互效率的秘密武器
第一章:框架的概述: MyBatis 框架的概述: MyBatis 是一个优秀的基于 Java 的持久框架,内部对 JDBC 做了封装,使开发者只需要关注 SQL 语句,而不关注 JDBC 的代码,使开发变得更加的简单MyBatis 通…...
选择困难?直接生成pynput快捷键字符串
from pynput import keyboard# 文档:https://pynput.readthedocs.io/en/latest/keyboard.html#monitoring-the-keyboard # 博客(pynput相关源码):https://blog.csdn.net/qq_39124701/article/details/145230331 # 虚拟键码(十六进制):https:/…...
DeepSeek-R1:强化学习驱动的推理模型
1月20日晚,DeepSeek正式发布了全新的推理模型DeepSeek-R1,引起了人工智能领域的广泛关注。该模型在数学、代码生成等高复杂度任务上表现出色,性能对标OpenAI的o1正式版。同时,DeepSeek宣布将DeepSeek-R1以及相关技术报告全面开源。…...
国内优秀的FPGA设计公司主要分布在哪些城市?
近年来,国内FPGA行业发展迅速,随着5G通信、人工智能、大数据等新兴技术的崛起,FPGA设计企业的需求也迎来了爆发式增长。很多技术人才在求职时都会考虑城市的行业分布和发展潜力。因此,国内优秀的FPGA设计公司主要分布在哪些城市&a…...
3.日常英语笔记
screening discrepancies 筛选差异 The team found some screening discrepancies in the data. 团队在数据筛选中发现了些差异。 Don’t tug at it ,or it will fall over and crush you. tug 拉,拽,拖 He tugged the door open with all his might…...
基于RIP的MGRE实验
实验拓扑 实验要求 按照图示配置IP地址配置静态路由协议,搞通公网配置MGRE VPNNHRP的配置配置RIP路由协议来传递两端私网路由测试全网通 实验配置 1、配置IP地址 [R1]int g0/0/0 [R1-GigabitEthernet0/0/0]ip add 15.0.0.1 24 [R1]int LoopBack 0 [R1-LoopBack0]i…...
【开源免费】基于Vue和SpringBoot的美食推荐商城(附论文)
本文项目编号 T 166 ,文末自助获取源码 \color{red}{T166,文末自助获取源码} T166,文末自助获取源码 目录 一、系统介绍二、数据库设计三、配套教程3.1 启动教程3.2 讲解视频3.3 二次开发教程 四、功能截图五、文案资料5.1 选题背景5.2 国内…...
Pandas DataFrame 拼接、合并和关联
拼接:使用 pd.concat(),可以沿着行或列方向拼接 DataFrame。 合并:使用 pd.merge(),可以根据一个或多个键进行不同类型的合并(左连接、右连接、全连接、内连接)。 关联:使用 join() 方法,通常在设置了索引的 DataFrame 上进行关联操作。 concat拼接 按列拼接 df1 = …...
【Redis】Redis修改连接数参数
1.重启操作背景 Redis数据库连接数上限,需要修改配置文件里maxclients参数,修改后需重启数据库 1.1、修改操作系统open files参数 1.2、修改redis连接数 2.登录操作系统 登录堡垒机 ssh {ip}3.查看当前状态 3.1、查看操作系统配置 ulimit -a3.2、…...
scratch变魔术 2024年12月scratch三级真题 中国电子学会 图形化编程 scratch三级真题和答案解析
目录 scratch变魔术 一、题目要求 1、准备工作 2、功能实现 二、案例分析 1、角色分析 2、背景分析 3、前期准备 三、解题思路 1、思路分析 2、详细过程 四、程序编写 五、考点分析 六、 推荐资料 1、入门基础 2、蓝桥杯比赛 3、考级资料 4、视频课程 5、py…...
51单片机开发:点阵屏显示数字
实验目标:在8x8的点阵屏上显示数字0。 点阵屏的原理图如下图所示,点阵屏的列接在P0端口,行接在74HC595扩展的DP端口上。 扩展口的使用详见:51单片机开发:IO扩展(串转并)实验-CSDN博客 要让点阵屏显示数字࿰…...
mysql DDL可重入讨论
mysql的bug:当执行 MySQL online DDL 时,期间如有其他并发的 DML 对相同的表进行增量修改,比如 update、insert、insert into … on duplicate key、replace into 等,且增量修改的数据违背唯一约束,那么 DDL 最后都会执…...
DAY01 面向对象回顾、继承、抽象类
学习目标 能够写出类的继承格式public class 子类 extends 父类{}public class Cat extends Animal{} 能够说出继承的特点子类继承父类,就会自动拥有父类非私有的成员 能够说出子类调用父类的成员特点1.子类有使用子类自己的2.子类没有使用,继承自父类的3.子类父类都没有编译报…...
127周一复盘 (165)玩法与难度思考
1.上午测试,小改了点东西, 基本等于啥也没干。 匆忙赶往车站。 从此进入春节期间,没有开发,而思考与设计。 2.火车上思考玩法与难度的问题。 目前的主流作法实际上并不完全符合不同玩家的需求, 对这方面还是要有自…...
【C语言常见概念详解】
目录 -----------------------------------------begin------------------------------------- 什么是C语言: 1. 基本数据类型 2. 变量与常量 3. 运算符与表达式 4. 控制结构 5. 函数 6. 指针 7. 数组与字符串 8. 结构体与联合体 9. 文件操作 结语 ----…...
弹性分组环——RPR技术
高频考点,考查20次: RPR与FDDI一样使用双环结构RPR环中的每一个节点都会执行SRP公平算法(非DPT、MPLS)传统的FDDI环,当源节点成功向目的结点发送一个数据帧后,这个数据帧由源结点从环中回收。但RPR环&#…...
定制Centos镜像
环境准备: 一台最小化安装的干净的系统,这里使用Centos7.9,一个Centos镜像,镜像也使用Centos7.9的。 [rootlocalhost ~]# cat /etc/system-release CentOS Linux release 7.9.2009 (Core) [rootlocalhost ~]# rpm -qa | wc -l 306 [rootloca…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)
在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马(服务器方面的)的原理,连接,以及各种木马及连接工具的分享 文件木马:https://w…...
论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
