【动态规划】数字三角形
算法提高课课堂笔记。
文章目录
- 摘花生
- 题意
- 思路
- 代码
- 最低通行费
- 题意
- 思路
- 代码
- 方格取数
- 题意
- 思路
- 代码
摘花生
题目链接
Hello Kitty想摘点花生送给她喜欢的米老鼠。
她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。
地里每个道路的交叉点上都有种着一株花生苗,上面有若干颗花生,经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走,不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。

输入格式
第一行是一个整数T,代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是两个整数,分别代表花生苗的行数R和列数 C。
每组数据的接下来R行数据,从北向南依次描述每行花生苗的情况。每行数据有C个整数,按从西向东的顺序描述了该行每株花生苗上的花生数目M。
输出格式
对每组输入数据,输出一行,内容为Hello Kitty能摘到得最多的花生颗数。
数据范围
1 ≤ T ≤ 100 , 1≤T≤100, 1≤T≤100,
1 ≤ R , C ≤ 100 , 1≤R,C≤100, 1≤R,C≤100,
0 ≤ M ≤ 1000 0≤M≤1000 0≤M≤1000
输入样例
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
输出样例
8
16
题意
从左上角走到右下角,求走过的交点最大权值和
思路
f[i][j]表示到达(i,j)点权重的最大值
因为只能向右走或向下走,所以到达(i,j)点的方式一定是:从左边的点向右走一步 / 从上面的点向下走一步
而左边的点权重最大值是f[i][j-1],上面的点权重最大值是f[i-1][j],从中取较大的,加上自身权值即可
代码
#include <bits/stdc++.h>using namespace std;const int N = 110;int n, m;
int w[N][N];
int f[N][N];int main()
{int tt;cin >> tt;while (tt -- ){cin >> n >> m;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )cin >> w[i][j];for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];cout << f[n][m] << '\n';}
}
最低通行费
原题链接
一个商人穿过一个 N × N N×N N×N 的正方形的网格,去参加一个非常重要的商务活动。
他要从网格的左上角进,右下角出。
每穿越中间 1 个小方格,都要花费 1 个单位时间。
商人必须在 ( 2 N − 1 ) (2N−1) (2N−1) 个单位时间穿越出去。
而在经过中间的每个小方格时,都需要缴纳一定的费用。
这个商人期望在规定时间内用最少费用穿越出去。
请问至少需要多少费用?
注意:不能对角穿越各个小方格(即,只能向上下左右四个方向移动且不能离开网格)。
输入格式
第一行是一个整数,表示正方形的宽度 N N N。
后面 N N N 行,每行 N N N 个不大于 100 的正整数,为网格上每个小方格的费用。
输出格式
输出一个整数,表示至少需要的费用。
数据范围
1 ≤ N ≤ 100 1≤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 109=1+2+5+7+9+12+19+21+33 109=1+2+5+7+9+12+19+21+33。
题意
从左上角走到右下角,不超过2n-1步,求权重之和最小值
思路
和上一题一样,都是左上角走到右下角
步数不超过2n-1,翻译过来就是不走回头路
只是把最大值改成了最小值
代码
#include <bits/stdc++.h>using namespace std;const int N = 110, inf = 0x3f3f3f3f;int n;
int w[N][N];
int f[N][N];int main()
{cin >> n;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )cin >> w[i][j];for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )if (i == 1 && j == 1) f[i][j] = w[i][j];else{f[i][j] = -inf;if (i > 1) f[i][j] = min(f[i][j], f[i - 1][j] + w[i][j]);if (j > 1) f[i][j] = min(f[i][j], f[i][j - 1] + w[i][j]);}cout << f[n][n] << '\n';
}
方格取数
题目链接
设有 N×N 的方格图,我们在其中的某些方格中填入正整数,而其它的方格中则放入数字0。如下图所示:

某人从图中的左上角 A 出发,可以向下行走,也可以向右行走,直到到达右下角的 B 点。
在走过的路上,他可以取走方格中的数(取走后的方格中将变为数字0)。
此人从 A 点到 B 点共走了两次,试找出两条这样的路径,使得取得的数字和为最大。
输入格式
第一行为一个整数 N N N,表示 N × N N×N N×N 的方格图。
接下来的每行有三个整数,第一个为行号数,第二个为列号数,第三个为在该行、该列上所放的数。
行和列编号从 1 开始。
一行“0 0 0”表示结束。
输出格式
输出一个整数,表示两条路径上取得的最大的和。
数据范围
N ≤ 10 N≤10 N≤10
输入样例
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[i1][j1][i2][j2]表示所有从(1,1)分别走到(i1,j1)(i2,j2)路径的最大值
如何处理同一个格子不被重复选择呢?
因为从左上角走到右下角,走的步数都是一样的,所以i1 + j1 == i2 + j2一定成立
所以我们可以将f[i1][j1][i2][j2]降维为f[k][i1][i2],k就是当前走过的步数
f[k][i1][i2]怎么计算呢?
分为四种情况:
- 第一条线路最后一步向下,第二条线路最后一步向下
f[k - 1][i1 - 1][i2 - 1] - 第一条线路最后一步向下,第二条线路最后一步向右
f[k - 1][i1 - 1][i2] - 第一条线路最后一步向右,第二条线路最后一步向下
f[k - 1][i1][i2 - 1] - 第一条线路最后一步向右,第二条线路最后一步向右
f[k - 1][i1][i2]
然后判断(i1,j1)和(i2,j2)是否重合,重合只用加 w[i1][j1],不重合需要加w[i1][j1] + w[i2][j2]
取最大值即可
代码
#include <bits/stdc++.h>using namespace std;const int N = 15;int n;
int w[N][N];
int f[N * 2][N][N];int main()
{cin >> n;int a, b, c;while (cin >> a >> b >> c, a || b || c) w[a][b] = c;for (int k = 2; k <= n * 2; k ++ )for (int i1 = 1; i1 <= n; i1 ++ )for (int i2 = 1; i2 <= n; i2 ++ ){int j1 = k - i1, j2 = k - i2;if (j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n){int t = w[i1][j1];if (i1 != i2) t += w[i2][j2];int &x = f[k][i1][i2];x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);x = max(x, f[k - 1][i1 - 1][i2] + t);x = max(x, f[k - 1][i1][i2 - 1] + t);x = max(x, f[k - 1][i1][i2] + t);}}cout << f[n + n][n][n] << '\n';
}
相关文章:
【动态规划】数字三角形
算法提高课课堂笔记。 文章目录 摘花生题意思路代码 最低通行费题意思路代码 方格取数题意思路代码 摘花生 题目链接 Hello Kitty想摘点花生送给她喜欢的米老鼠。 她来到一片有网格状道路的矩形花生地(如下图),从西北角进去,东南角出来。 地里每个道…...
【C++】开源:ceres和g2o非线性优化库配置使用
😏★,:.☆( ̄▽ ̄)/$:.★ 😏 这篇文章主要介绍ceres和g2o非线性优化库配置使用。 无专精则不能成,无涉猎则不能通。——梁启超 欢迎来到我的博客,一起学习,共同进步。 喜欢的朋友可以关注一下&…...
OCR学习
...
《练习100》56~60
题目56 M 5 a [1, 2, 3, 4, 5] i 1 j M - 1 while i < M:# print(f"第{i1}轮交换前:i {i}, j {j} , a[{i}] {a[i]} , a[{j}] {a[j]}")a[i], a[j] a[j], a[i]# print(f"第{i1}轮交换后:i {i}, j {j} , a[{i}] {a[i]} , a[…...
基于大数据为底层好用准确性高的竞彩足球比分预测进球数分析软件介绍推荐
大数据与贝叶斯理论在足球比赛分析与预测中的应用 随着科技的不断进步,大数据分析在各个领域的应用也越来越广泛,其中包括体育竞技。足球比赛作为全球最受欢迎的运动之一,也借助大数据和贝叶斯理论来进行模型分析和预测。本文将通过结合贝叶…...
Django进阶
1.orm 1.1 基本操作 orm,关系对象映射。 类 --> SQL --> 表 对象 --> SQL --> 数据特点:开发效率高、执行效率低( 程序写的垃圾SQL )。 编写ORM操作的步骤: settings.py,连…...
Linux系统服务管理
服务命令比较 操作 Linux 6 Linux7 服务开机自动启动 chkconfig --level 35 iptables on systemctl enable firewalld.service 服务器开机不自动启动 chkconfig --level 35 iptables off systemctl disable firewalld.service 加入自定义服务 chkconfig --add aaa s…...
C#之控制台版本得贪吃蛇
贪吃蛇小时候大家都玩过,具体步骤如下: 1.给游戏制造一个有限得空间。 2.生成墙壁,小蛇碰撞到墙壁或者咬到自己的尾巴,游戏结束。 3.生成随机的食物。 4.吃掉食物,增加自身的体长,并生成新的食物。 具体代码如下&…...
ffplay数据结构分析(一)
本文为相关课程的学习记录,相关分析均来源于课程的讲解,主要学习音视频相关的操作,对字幕的处理不做分析 下面我们对ffplay的相关数据结构进行分析,本章主要是对PacketQueue的讲解 struct MyAVPacketList和PacketQueue队列 ffp…...
JavaWeb学习|JSP相关内容
1.什么是JSP Java Server Pages: Java服务器端页面,也和Servlet一样,用于动态Web技术! 最大的特点: 。写JSP就像在写HTML 。区别: 。HTML只给用户提供静态的数据 。JSP页面中可以嵌入JAVA代码,为用户提供动态数据 JSP最终也会被转换成为一…...
Springboot后端通过路径映射获取本机图片资源
项目场景: 项目中对图片的处理与查看是必不可少的,本文将讲解如何通过项目路径来获取到本机电脑的图片资源 如图所示,在我的本机D盘的图片测试文件夹(文件夹名字不要有中文)下有一些图片, 我们要在浏览器上访问到这些图片&#…...
【IDEA + Spark 3.4.1 + sbt 1.9.3 + Spark MLlib 构建鸢尾花决策树分类预测模型】
决策树进行鸢尾花分类的案例 背景说明: 通过IDEA Spark 3.4.1 sbt 1.9.3 Spark MLlib 构建鸢尾花决策树分类预测模型,这是一个分类模型案例,通过该案例,可以快速了解Spark MLlib分类预测模型的使用方法。 依赖 ThisBuild /…...
亚马逊 EC2服务器下部署java环境
1. jdk 1.8 安装 1.1 下载jdk包 官网 Java Downloads | Oracle tar.gz 包 下载下来 1.2 本地连接 服务器 我用的是亚马逊的ec2 系统是 ubuntu 的 ssh工具是 Mobaxterm , 公有dns 创建实例时的秘钥 链接 Mobaxterm 因为使用的 ubuntu 所以登录的 名称 就是 ubuntu 然后 …...
CTF流量题解http1.pcapng
使用Wireshark工具打开流量文件http1.pcapng,如下图所示。 在过滤检索栏输入http,wireshark自动进行过滤。...
若依vue前端有全局用户信息变量吗
"若依"是一个基于SpringBoot和Vue的前后端分离的开源项目。在前端Vue部分,全局用户信息通常保存在Vuex中,Vuex是Vue.js的状态管理模式。它提供了一个集中式存储来管理所有组件的状态,并以相应的规则保证状态以一种可预测的方式发生…...
什么是Milvus
原文出处:https://www.yii666.com/blog/393941.html 什么是Milvus Milvus 是一款云原生向量数据库,它具备高可用、高性能、易拓展的特点,用于海量向量数据的实时召回。 Milvus 基于 FAISS、Annoy、HNSW 等向量搜索库构建,核心是…...
如何快速实现三菱FX3U程序的无线下载?
1.系统概述 三菱PLC FX3u可以使用专用下载线通过计算机串口下载程序,同样也可以使用自制下载线缆,连接无线模块 DTD435M进行远程无线下载程序,计算机端采用RS232或者RS485 将计算机端与无线模块连接,PLC端同样使用RS232转RS485将…...
Flink源码之RPC
Flink是一个典型的Master/Slave分布式实时处理系统,分布式系统组件之间必然涉及通信,也即RPC,以下图展示Flink组件之间的关系: RPCGateWay 一般RPC框架可根据用户业务类生成客户端和服务器端通信底层代码,此时只需定…...
【LeetCode 75】第二十四题(2390)从字符串中移除星号
目录 题目: 示例: 分析: 代码运行结果: 题目: 示例: 分析: 题目给我们一个字符串,然后字符串中包含星号*,要求每个星号消除一个从星号左边起最近的一个字符…...
通向架构师的道路之weblogic的集群与配置
一、Weblogic的集群 还记得我们在第五天教程中讲到的关于Tomcat的集群吗? 两个tomcat做node即tomcat1, tomcat2,使用Apache HttpServer做请求派发。 现在看看WebLogic的集群吧,其实也差不多。 区别在于: Tomcat的集群的实现为两个物理上…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台
🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...
STM32HAL库USART源代码解析及应用
STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...
iview框架主题色的应用
1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题,无需引入,直接可…...
宇树科技,改名了!
提到国内具身智能和机器人领域的代表企业,那宇树科技(Unitree)必须名列其榜。 最近,宇树科技的一项新变动消息在业界引发了不少关注和讨论,即: 宇树向其合作伙伴发布了一封公司名称变更函称,因…...
