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

动态规划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的正方形的网格&#xff0c;去参加一个非常重要的商务活动。 他要从网格的左上角进&#xff0c;右下角出。每穿越中间 1个小方格&#xff0c;都要花费 1个单位时间。商人必须在 (2N−1)个单位…...

deepseek R1的确不错,特别是深度思考模式

deepseek R1的确不错&#xff0c;特别是深度思考模式&#xff0c;每次都能自我反省改进。比如我让 它写文案&#xff1a; 【赛博朋克版程序员新春密码——2025我们来破局】 亲爱的代码骑士们&#xff1a; 当CtrlS的肌肉记忆遇上抢票插件&#xff0c;当Spring Boot的…...

Linux 常用命令 - sort 【对文件内容进行排序】

简介 sort 命令源于英文单词 “sort”&#xff0c;表示排序。其主要功能是对文本文件中的行进行排序。它可以根据字母、数字、特定字段等不同的标准进行排序。sort 通过逐行读取文件&#xff08;没有指定文件或指定文件为 - 时读取标准输入&#xff09;内容&#xff0c;并按照…...

MyBatis最佳实践:提升数据库交互效率的秘密武器

第一章&#xff1a;框架的概述&#xff1a; MyBatis 框架的概述&#xff1a; MyBatis 是一个优秀的基于 Java 的持久框架&#xff0c;内部对 JDBC 做了封装&#xff0c;使开发者只需要关注 SQL 语句&#xff0c;而不关注 JDBC 的代码&#xff0c;使开发变得更加的简单MyBatis 通…...

选择困难?直接生成pynput快捷键字符串

from pynput import keyboard# 文档&#xff1a;https://pynput.readthedocs.io/en/latest/keyboard.html#monitoring-the-keyboard # 博客(pynput相关源码)&#xff1a;https://blog.csdn.net/qq_39124701/article/details/145230331 # 虚拟键码(十六进制)&#xff1a;https:/…...

DeepSeek-R1:强化学习驱动的推理模型

1月20日晚&#xff0c;DeepSeek正式发布了全新的推理模型DeepSeek-R1&#xff0c;引起了人工智能领域的广泛关注。该模型在数学、代码生成等高复杂度任务上表现出色&#xff0c;性能对标OpenAI的o1正式版。同时&#xff0c;DeepSeek宣布将DeepSeek-R1以及相关技术报告全面开源。…...

国内优秀的FPGA设计公司主要分布在哪些城市?

近年来&#xff0c;国内FPGA行业发展迅速&#xff0c;随着5G通信、人工智能、大数据等新兴技术的崛起&#xff0c;FPGA设计企业的需求也迎来了爆发式增长。很多技术人才在求职时都会考虑城市的行业分布和发展潜力。因此&#xff0c;国内优秀的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 拉&#xff0c;拽&#xff0c;拖 He tugged the door open with all his might…...

基于RIP的MGRE实验

实验拓扑 实验要求 按照图示配置IP地址配置静态路由协议&#xff0c;搞通公网配置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 &#xff0c;文末自助获取源码 \color{red}{T166&#xff0c;文末自助获取源码} T166&#xff0c;文末自助获取源码 目录 一、系统介绍二、数据库设计三、配套教程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数据库连接数上限&#xff0c;需要修改配置文件里maxclients参数&#xff0c;修改后需重启数据库 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单片机开发:点阵屏显示数字

实验目标&#xff1a;在8x8的点阵屏上显示数字0。 点阵屏的原理图如下图所示&#xff0c;点阵屏的列接在P0端口&#xff0c;行接在74HC595扩展的DP端口上。 扩展口的使用详见&#xff1a;51单片机开发&#xff1a;IO扩展(串转并)实验-CSDN博客 要让点阵屏显示数字&#xff0…...

mysql DDL可重入讨论

mysql的bug&#xff1a;当执行 MySQL online DDL 时&#xff0c;期间如有其他并发的 DML 对相同的表进行增量修改&#xff0c;比如 update、insert、insert into … on duplicate key、replace into 等&#xff0c;且增量修改的数据违背唯一约束&#xff0c;那么 DDL 最后都会执…...

DAY01 面向对象回顾、继承、抽象类

学习目标 能够写出类的继承格式public class 子类 extends 父类{}public class Cat extends Animal{} 能够说出继承的特点子类继承父类,就会自动拥有父类非私有的成员 能够说出子类调用父类的成员特点1.子类有使用子类自己的2.子类没有使用,继承自父类的3.子类父类都没有编译报…...

127周一复盘 (165)玩法与难度思考

1.上午测试&#xff0c;小改了点东西&#xff0c; 基本等于啥也没干。 匆忙赶往车站。 从此进入春节期间&#xff0c;没有开发&#xff0c;而思考与设计。 2.火车上思考玩法与难度的问题。 目前的主流作法实际上并不完全符合不同玩家的需求&#xff0c; 对这方面还是要有自…...

【C语言常见概念详解】

目录 -----------------------------------------begin------------------------------------- 什么是C语言&#xff1a; 1. 基本数据类型 2. 变量与常量 3. 运算符与表达式 4. 控制结构 5. 函数 6. 指针 7. 数组与字符串 8. 结构体与联合体 9. 文件操作 结语 ----…...

弹性分组环——RPR技术

高频考点&#xff0c;考查20次&#xff1a; RPR与FDDI一样使用双环结构RPR环中的每一个节点都会执行SRP公平算法&#xff08;非DPT、MPLS&#xff09;传统的FDDI环&#xff0c;当源节点成功向目的结点发送一个数据帧后&#xff0c;这个数据帧由源结点从环中回收。但RPR环&#…...

定制Centos镜像

环境准备&#xff1a; 一台最小化安装的干净的系统&#xff0c;这里使用Centos7.9,一个Centos镜像&#xff0c;镜像也使用Centos7.9的。 [rootlocalhost ~]# cat /etc/system-release CentOS Linux release 7.9.2009 (Core) [rootlocalhost ~]# rpm -qa | wc -l 306 [rootloca…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...