动态规划入门(数字三角形模型)

备战2024年蓝桥杯&算法学习 -- 每日一题
Python大学A组

        试题一:摘花生
        试题二:最低通行费用
        试题三:方格取数
        试题四:传纸条


试题一:摘花生

【题目描述】

        Hello Kitty想摘点花生送给她喜欢的米老鼠。她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过一株花生苗就能摘走该它上面所有的花生。Hello Kitty只能向东或向南走,不能向西或向北走。问Hello Kitty最多能够摘到多少颗花生。

【输入格式】

        第一行是一个整数T,代表一共有多少组数据。

        接下来是T组数据。

        每组数据的第一行是两个整数,分别代表花生苗的行数R和列数 C。

        每组数据的接下来R行数据,从北向南依次描述每行花生苗的情况。每行数据有C个整数,按从西向东的顺序描述了该行每株花生苗上的花生数目M。

【输出格式】

        对每组输入数据,输出一行,内容为Hello Kitty能摘到得最多的花生颗数。

【数据范围】

        1≤T≤100,
        1≤R,C≤100,
        0≤M≤1000

【输入样例】

2
2 2
1 1
3 4
2 3
2 3 4
1 6 5

【输出样例】

8
16

【解题思路】

        线性DP中的数字三角形模型,基础模型,状态转移方程f[i][j] = max(f[i-1][j] , f[i][j-1]) + w[i][j]。

【Python程序代码】

T = int(input())
for _ in range(T):r,c = map(int,input().split())a = [[0]*(c+5)]for i in range(r):a.append([0]+list(map(int,input().split())))f = [[0]*(c+5) for _ in range(r+5)]for i in range(1,r+1):for j in range(1,c+1):f[i][j] = max(f[i-1][j],f[i][j-1])+a[i][j]print(f[r][c])

试题二:最低通行费用

【题目描述】

        本题大意上给定一个 n×n的矩阵,让我们从左上角出发,最终走到右下角走过的方块数量的不能超过 2n−1个求所有路线中,经过的方块的总价值最少的路线。

【解题思路】

        和上一题相比改了一些条件,比如增加了一个不能超过2n-1个方块,考虑一下(1,1)到(n,n)的曼哈顿距离发现d = 2*n-2,同时题目要求的是求总价值最小,在2*n-2的最短路径上加上一个方块一定会大于等于这2*n-2个方块的价值,所以本题可以套上面题目的板子。

【Python程序代码】

n = int(input())
f = [[1e9]*(n+5) for _ in range(n+5)]
a = [[0]*(n+5)]
for i in range(n):a.append([0]+list(map(int,input().split())))
f[0][1]=f[1][0]=0
for i in range(1,n+1):for j in range(1,n+1):f[i][j] = min(f[i][j-1],f[i-1][j])+a[i][j]
print(f[n][n])

试题三:方格取数

【题目描述】

        设有N×N 的方格图(N≤9),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字 0。如下图所示(见样例):

         某人从图的左上角的 A 点出发,可以向下行走,也可以向右走,直到到达右下角的 B 点。在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字 0)。
        此人从 A 点到 B 点共走两次,试找出 2 条这样的路径,使得取得的数之和为最大。

【输入数据】

        输入的第一行为一个整数 N(表示 N×N 的方格图),接下来的每行有三个整数,前两个表示位置,第三个数为该位置上所放的数。一行单独的 0 表示输入结束。

【输出数据】

        只需输出一个整数,表示 2 条路径上取得的最大的和。

【输入样例】

8
2 3 13
2 6  6
3 5  7
4 4 14
5 2 21
5 6  4
6 3 15
7 2 14
0 0  0

【输出样例】

67

【解题思路】

        需要考虑两条路径,如何考虑更好呢?如果说分别考虑的话如何判断是否重合呢且这两者相加也不一定是最大值,所以如果能够同时考虑两条路就好了,首先两条路的曼哈顿距离一定是相等的,所以我们可以考虑枚举每一条路径走的行的数量,列的数量可以用曼哈顿距离-列的数量,所以f[k][i][j]表示曼哈顿距离为k,且第一条路径走了i行k-i列,第二条路径走了j行k-j列,那么如何考虑状态转移呢?每一个f[k][i][j]可以由第一条路径往右走或者往下走过来,也即使f[k-1][i][j]和f[k-1][i-1][j],第二条路径也是往右或往下,f[k-1][i][j],f[k-1][i][j-1],那也就是四种状态:f[k-1][i-1][j-1]、f[k-1][i][j-1]、f[k-1][i-1][j]、f[k-1][i][j]。

【Python程序代码】

n = int(input())
w = [[0]*(n+5) for _ in range(n+5)]
a,b,c = map(int,input().split())
while not (a==0 and b==0 and c==0):w[a][b] += ca, b, c = map(int, input().split())
f = [[[0]*(n+5) for _ in range(n+5)] for i in range(2*n+5)]
for k in range(2,2*n+1):for i in range(1,n+1):for j in range(1,n+1):if k-i<=0 or k-j<=0 or k-i>n or k-j>n:continuev = w[i][k-i]t = f[k][i][j]if i!=j:v+=w[j][k-j]t = max(t, f[k-1][i-1][j-1])t = max(t, f[k-1][i][j-1])t = max(t, f[k-1][i-1][j])t = max(t, f[k-1][i][j])f[k][i][j] = t+v
print(f[2*n][n][n])

试题四:传纸条

【题目描述】

        小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学安排坐成一个 m 行 n 列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里,小渊坐在矩阵的左上角,坐标 (1,1),小轩坐在矩阵的右下角,坐标 (m,n)。从小渊传到小轩的纸条只可以向下或者向右传递,从小轩传给小渊的纸条只可以向上或者向左传递。 在活动进行中,小渊希望给小轩传递一张纸条,同时希望小轩给他回复。班里每个同学都可以帮他们传递,但只会帮他们一次,也就是说如果此人在小渊递给小轩纸条的时候帮忙,那么在小轩递给小渊的时候就不会再帮忙,反之亦然。 还有一件事情需要注意,全班每个同学愿意帮忙的好感度有高有低(注意:小渊和小轩的好心程度没有定义,输入时用 0 表示),可以用一个 0∼100的自然数来表示,数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条,即找到来回两条传递路径,使得这两条路径上同学的好心程度之和最大。现在,请你帮助小渊和小轩找到这样的两条路径。

【输入格式】

        第一行有 2 个用空格隔开的整数 m 和 n,表示学生矩阵有 m 行 n 列。

        接下来的 m 行是一个 m×n 的矩阵,矩阵中第 i 行 j 列的整数表示坐在第 i 行 j 列的学生的好心程度,每行的 n 个整数之间用空格隔开。

【输出格式】

        输出一个整数,表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

 【数据范围】

        1≤n,m≤50

【输入样例】

3 3
0 3 9
2 8 5
5 7 0

【输出样例】

34

【解题思路】

        和上面一题类似,多了一个路径不可重复,考虑一下用上面的方法做一下得到两条路径,如果路径没有交叉和重叠点那么上面的就是答案。如果有交叉呢。

        对于有交叉的我们可以通过移动变到没有交叉但是个别点重合。对于重复,我们必然可以在两条路线中找到额外的一条或两条路线,使得新的路线不发生重合。如下图:

        由于原路线是最优解,则必然 wA=wB=0,否则最优解路径必然是经过A或B的,因此,我们可以通过微调其中的一条路线,使之不经过重合点 C,同时路线的总价值没有减少。所以可以直接用方格取数的方法。

【Python程序代码】

n,m = map(int,input().split())
a = [[0]*(m+5)]
for i in range(n):a.append([0]+list(map(int,input().split())))
f = [[[0]*(n+5) for i in range(n+5)] for j in range(n+m+5)]
for k in range(2,n+m+1):for i in range(1,n+1):for j in range(1,n+1):if k-i>m or k-i<=0 or k-j>m or k-j<=0:continuet = f[k][i][j]v = a[i][k-i]if i!=j:v+=a[j][k-j]t = max(t, f[k-1][i-1][j-1])t = max(t, f[k-1][i-1][j])t = max(t, f[k-1][i][j-1])t = max(t, f[k-1][i][j])f[k][i][j] = t+v
print(f[n+m][n][n])

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/290331.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

持续集成流水线介绍(CI)

目录 一、概述 二、持续集成的典型操作流程 2.1 概述 2.2 持续集成的操作流程图 2.3 持续集成关键流程说明 三、构建持续集成流水线的方式 3.1 依托云厂商能力 3.2 采用开源产品 3.3 企业自研 四、构建持续化集成流水线 4.1 基于GitHub的持续集成流水线&#xff08;公…

Java毕业设计-基于springboot开发的招聘信息管理系统平台-毕业论文+答辩PPT(附源代码+演示视频)

文章目录 前言一、毕设成果演示&#xff08;源代码在文末&#xff09;二、毕设摘要展示1、开发说明2、需求分析3、系统功能结构 三、系统实现展示1、系统功能模块2、管理员功能模块3、企业后台管理模块4、用户后台管理模块 四、毕设内容和源代码获取总结 Java毕业设计-基于spri…

Tomcat项目创建 以及 在IDEA当中集成Tomcat

一: 有关Tomcat的WEB项目创建 TOMCAT项目的创建有两种方式, 第一种是利用骨架进行创建, 第二种是利用填补进行相应的创建, 不适用骨架进行创建 ,在这里主要聊第二种 (使用IDEA版本为2023) 1. 创建MAVEN项目, 非骨架形式 2.在相应的pom文件当中设置打包方式 为 war包的打包形…

快速上手Spring Cloud 十四:璀璨物联网之路

快速上手Spring Cloud 一&#xff1a;Spring Cloud 简介 快速上手Spring Cloud 二&#xff1a;核心组件解析 快速上手Spring Cloud 三&#xff1a;API网关深入探索与实战应用 快速上手Spring Cloud 四&#xff1a;微服务治理与安全 快速上手Spring Cloud 五&#xff1a;Spring …

|行业洞察·汽车|《2024新能源汽车行业及营销趋势报告-20页》

报告的主要内容解读&#xff1a; 新能源汽车行业概述及品牌分布&#xff1a; 近年来&#xff0c;中国新能源汽车销量增速高&#xff0c;市场占有率快速提升&#xff0c;成为汽车行业的重要增量。新能源汽车消费者趋向年轻化、女性化和高端化&#xff0c;对高科技、新体验有较高…

获取高德安全码SHA1

高德开发者平台上给的三种方法 获取安全码SHA1&#xff0c;这里我自己使用的是第三种方法。 1、通过Eclipse编译器获取SHA1 使用 adt 22 以上版本&#xff0c;可以在 eclipse 中直接查看。 Windows&#xff1a;依次在 eclipse 中打开 Window -> Preferances -> Androi…

C#手术麻醉信息系统全套商业源码,自主版权,支持二次开发 医院手麻系统源码

手术麻醉信息系统是HIS产品的中的一个组成部分&#xff0c;主要应用于医院的麻醉科&#xff0c;属于电子病历类产品。医院麻醉监护的功能覆盖整个手术与麻醉的全过程&#xff0c;包括手术申请与排班、审批、安排、术前、术中和术后的信息管理提供支持。 手术麻醉信息系统可与EM…

Node爬虫:原理简介

在数字化时代&#xff0c;网络爬虫作为一种自动化收集和分析网络数据的技术&#xff0c;得到了广泛的应用。Node.js&#xff0c;以其异步I/O模型和事件驱动的特性&#xff0c;成为实现高效爬虫的理想选择。然而&#xff0c;爬虫在收集数据时&#xff0c;往往面临着诸如反爬虫机…

编译与链接(想了解编译与链接,那么看这一篇就足够了!)

前言&#xff1a;在我们练习编程的时候&#xff0c;我们只需要将代码写入、运行&#xff0c;就可以得到计算之后的结果了&#xff0c;但是你有没有想过&#xff0c;为什么就可以得到计算之后的结果呢&#xff0c;它的底层又到底是什么呢&#xff1f; ✨✨✨这里是秋刀鱼不做梦的…

​python学习之变量类型​

print单纯输中的十种数据类型只需要用print()函数即可&#xff0c;()里面直接写变量名。 下面重点介绍print格式输出&#xff1a; 第一种方法&#xff1a;一个萝卜一个坑&#xff0c;下面的代码中&#xff0c;{0}、{1}、{2}分别表示j,i,j*i&#xff0c;单引号里面是输出格式。…

postgis已有表插入外部表数据带空间字段和主键

1、postgis已有表 其中gid是主键字段,geom是几何字段 2、待插入表的数据(分三种情况) (1)通过坐标将写入几何类型字段 INSERT INTO test (gid, geom, mc,lng,lat) SELECT (SELECT COALESCE(MAX(gid)<

Linux的学习之路:3、基础指令(2)

一、echo指令 这个指令在上篇文章我也用了但是忘了说了&#xff0c;这个指令的大概用法就是把后面跟的文本等输出在显示器上&#xff0c;如下代码所示打印的“Hello Linux” [rootVM-24-9-centos ~]# echo "Hello Linux" Hello Linux二、输出重定向与输入重定向 着…

面向对象:继承

文章目录 一、什么叫继承&#xff1f;二、单继承三、多继承3.1多继承的各种情况3.1.1一般情况3.1.1特殊情况&#xff08;菱形继承&#xff09; 四、菱形继承引发的问题4.1 问题1:数据冗余4.2 问题2:二义性&#xff08;无法确定到底是访问哪个&#xff09; 五、虚拟继承解决菱形…

vue前端工程化

前言 本文介绍的是有关于vue方面的前端工程化实践&#xff0c;主要通过实践操作让开发人员更好的理解整个前端工程化的流程。 本文通过开发准备阶段、开发阶段和开发完成三个阶段开介绍vue前端工程化的整体过程。 准备阶段 准备阶段我将其分为&#xff1a;框架选择、规范制…

【MySQL】数据库--表操作

目录 一、创建表 二、查看表 三、修改表 1. 添加字段--add 2.修改表名--rename to 3.修改列名--change 4.修改字段的数据类型--modify 5.删除字段&#xff08;列&#xff09;--drop 四、删除表 一、创建表 create [temporary]table[if not exists]table_name [([colu…

SQL Server 实验二:数据库视图的创建和使用

目录 第一关 相关知识 什么是表 操作数据表 创建数据表 插入数据 修改表结构 删除数据表 编程要求 第一关实验代码&#xff1a; 第二关 相关知识 视图是什么 视图的优缺点 视图的优点 视图的缺点 操作视图 创建视图 通过视图向基本表中插入数据 通过视图修改基本表的…

TOP100-回溯(二)

4.39. 组合总和 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target &#xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 &#xff0c;并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制…

Vue的前世今生与安装配置

vue的前世今生 Vue.js是一个流行的前端JavaScript框架&#xff0c;用于构建用户界面与单页应用程序&#xff08;SPA&#xff09;。它的诞生和发展可以概括为以下几个重要阶段&#xff1a; 初创阶段&#xff1a;Vue由中国人尤雨溪&#xff08;Evan You&#xff09;创建于2014年…

目标检测+车道线识别+追踪

一种方法&#xff1a; 车道线检测-canny边缘检测-霍夫变换 一、什么是霍夫变换 霍夫变换&#xff08;Hough Transform&#xff09;是一种在图像处理和计算机视觉中广泛使用的特征检测技术&#xff0c;主要用于识别图像中的几何形状&#xff0c;尤其是直线、圆和椭圆等常见形状…

Mysql数据库-DQL查询

Mysql数据库-DQL基本查询 1 DQL基本查询1.1 基础查询1.2 WHERE子句1&#xff09;算术运算符2&#xff09;逻辑运算符3&#xff09;比较运算符A&#xff09;BETWEEN... AND ...B&#xff09;IN(列表)C&#xff09;NULL值判断 4&#xff09;综合练习 2 DQL高级查询2.1 LIKE 模糊查…