动态规划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…...
Phi-4-mini-reasoning应用场景:AI竞赛教练系统自动出题与解析
Phi-4-mini-reasoning应用场景:AI竞赛教练系统自动出题与解析 1. 引言:当AI遇见竞赛训练 想象一下,一位数学竞赛教练每天需要: 设计不同难度的题目准备详细的解题步骤针对学生错误提供个性化解析不断更新题库保持新鲜度 传统方…...
忍者像素绘卷微信小程序云开发实践:Serverless生成服务架构
忍者像素绘卷微信小程序云开发实践:Serverless生成服务架构 1. 项目背景与核心价值 忍者像素绘卷是一款基于微信小程序平台的云端图像生成工具,采用Serverless架构实现。它将传统漫画创作与AI技术相结合,为用户提供简单高效的像素艺术创作体…...
南北阁Nanbeige 4.1-3B效果展示:同一问题在不同temperature设置下的风格对比
南北阁Nanbeige 4.1-3B效果展示:同一问题在不同temperature设置下的风格对比 1. 引言:为什么关注temperature参数? 如果你用过AI对话工具,可能会发现一个有趣的现象:同一个问题,有时候AI的回答严谨专业&a…...
intv_ai_mk11惊艳输出集:RAG技术通俗解释、电商详情页开头、朋友圈爆款文案
intv_ai_mk11惊艳输出集:RAG技术通俗解释、电商详情页开头、朋友圈爆款文案 1. 什么是intv_ai_mk11 AI对话机器人 intv_ai_mk11是一款基于7B参数Llama架构的AI对话助手,运行在GPU服务器上。它能够理解自然语言并生成高质量的文本回复,适用于…...
OpenClaw旅行规划专家:Qwen3-14b_int4_awq自动生成行程表与预订提醒
OpenClaw旅行规划专家:Qwen3-14b_int4_awq自动生成行程表与预订提醒 1. 为什么需要AI旅行规划助手 每次计划旅行时,我总会被各种琐事淹没:查天气、比价酒店、确认景点开放时间、安排交通路线……这些重复劳动既耗时又容易出错。直到上个月尝…...
SEO_10个提升网站排名的SEO技巧与实战方法
SEO:10个提升网站排名的SEO技巧与实战方法 在当今数字化时代,网站排名不仅关乎网站的曝光率,更影响到业务的发展。因此,提升网站排名(SEO)成为了每一个网站主的首要任务。有哪些SEO技巧能够帮助提升网站的排名呢&…...
《QGIS快速入门与应用基础》256:SVG格式:适合矢量图二次编辑
作者:翰墨之道,毕业于国际知名大学空间信息与计算机专业,获硕士学位,现任国内时空智能领域资深专家、CSDN知名技术博主。多年来深耕地理信息与时空智能核心技术研发,精通 QGIS、GrassGIS、OSG、OsgEarth、UE、Cesium、OpenLayers、Leaflet、MapBox 等主流工具与框架,兼具…...
2026届毕业生推荐的十大降重复率神器解析与推荐
Ai论文网站排名(开题报告、文献综述、降aigc率、降重综合对比) TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 降低AIGC痕迹的关键之处在于去除机器生成的那种模式化特性,如果要采用避免使用过…...
渗流完美降雨边界:单、双重渗透介质降雨边界处理的改进探索
渗流完美降雨边界——基于单、双重渗透介质降雨边界处理的改进 [1]模型简介:使用数值模拟软件COMSOL复现论文(窦智,刘一民,周志芳,等.基于单、双重渗透介质降雨边界处理的改进[J].岩土力学,2022,43(03):789-798.),该文献针对传统降…...
短视频 SEO 优化能给企业带来什么好处_短视频 SEO 如何优化视频标题和描述
短视频 SEO 优化能给企业带来什么好处_短视频 SEO 如何优化视频标题和描述 在当今数字化时代,短视频平台已经成为了企业营销和品牌推广的重要渠道。短视频的传播范围和影响力远不止于视频内容本身,背后的搜索引擎优化(SEO)策略同…...
