动态规划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…...
OpenClaw+Phi-3-vision-128k-instruct安全方案:敏感数据本地化处理指南
OpenClawPhi-3-vision-128k-instruct安全方案:敏感数据本地化处理指南 1. 为什么需要本地化处理敏感数据? 上周我帮一位做财务咨询的朋友处理季度报表时,他提到一个痛点:每次用云端AI工具分析客户财务数据都提心吊胆。这让我意识…...
Elasticsearch-PHP异步搜索终极指南:如何实现高性能搜索应用
Elasticsearch-PHP异步搜索终极指南:如何实现高性能搜索应用 【免费下载链接】elasticsearch-php Official PHP client for Elasticsearch. 项目地址: https://gitcode.com/gh_mirrors/el/elasticsearch-php Elasticsearch-PHP是官方PHP客户端,为…...
NVIDIA Profile Inspector深度解析:解锁显卡隐藏性能与高级配置实战指南
NVIDIA Profile Inspector深度解析:解锁显卡隐藏性能与高级配置实战指南 【免费下载链接】nvidiaProfileInspector 项目地址: https://gitcode.com/gh_mirrors/nv/nvidiaProfileInspector NVIDIA Profile Inspector是一款面向技术爱好者和开发者的专业显卡配…...
Axios 近期安全版本
在执行 npm i 的时候最好执行指定版本:影响版本axios (npm) 0.30.4axios (npm) 1.14.1plain-crypto-js (npm) 4.2.1安全版本axios (npm) < 0.30.3axios (npm) < 1.14.0axios (npm) > 0.30.4axios (npm) > 1.14.1plain-crypto-js (npm) 恶意包已被 np…...
SwartNinjaPIR:嵌入式高可靠PIR运动检测驱动库
1. SwartNinjaPIR 库概述:面向嵌入式系统的高可靠性 PIR 运动检测驱动设计SwartNinjaPIR 是一个专为 Arduino 及兼容平台(如 STM32、ESP32 等基于 Arduino Core 的 MCU)设计的轻量级、生产就绪型被动红外(Passive Infrared, PIR&a…...
NSSCTF做题记录十 | [巅峰极客 2022 决赛]开端:strangeTempreture
[巅峰极客 2022 决赛]开端:strangeTempreture随便点击一个流量包,右击点击追踪流,TCP 流把这几个字母拼接到一起,下面还有很多ZmxhZ3s5N2JmZWIwMy1mYTVjLWFhNmYtYWQxZS05YzVkMzhjNzQ0OWV9base64 解码,得到 flagflag{97…...
STM32CubeMX + EG2131预驱芯片:搞定无刷电机六步换向的硬件配置避坑指南
STM32CubeMX与EG2131预驱芯片的无刷电机六步换向实战解析 引言 在嵌入式电机控制领域,无刷直流电机(BLDC)因其高效率、长寿命和低维护成本等优势,正逐步取代传统有刷电机。然而,当工程师们从理论转向实践时,…...
ESP32 -espidf 实战:利用AW9523实现16路PWM调光与高电流驱动
1. 为什么需要AW9523扩展芯片? ESP32作为一款功能强大的物联网芯片,其GPIO资源在实际项目中经常捉襟见肘。做过智能照明项目的朋友应该深有体会,当我们需要控制多个LED灯带时,ESP32自带的PWM通道根本不够用。我曾经在一个商业照明…...
8元和3元的降AI工具差在哪用数据说话
降AI率工具市场里,价格跨度很大:有3元/千字的,有8元/千字的,差了2.5倍。 很多同学的第一反应是"贵的肯定好",但这个逻辑在降AI工具领域不一定成立。这篇文章用实测数据说话,对比比话降AI&#x…...
UniApp项目实战:手把手教你用云函数搞定UniPush 2.0服务端消息推送
UniPush 2.0云函数实战:从零构建高可用消息推送系统 在移动应用生态中,消息推送是维系用户活跃度的关键触达手段。UniPush 2.0作为DCloud推出的新一代推送服务,通过云函数与厂商通道的深度整合,解决了传统推送方案中离线到达率低、…...
