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

C++知识点总结(58)：序列型动态规划

news 来源：原创 2025/7/27 20:06:39

动态规划Ⅰ

一、基础
- 1. 意义
- 2. 序列 dp 解法
二、例题
- 1. 最大子段和
- 2. 删数最大子段和（数据强度：pro max）
- 3. 最长上升子序列（数据强度：pro max）
- 4. 3 或 5 的倍数序列
- 5. 数码约数序列

一、基础

1. 意义

动态规划（dynamic programming，简称 dp），将一个目标大问题“大事化小，小事化了”，分成很多的子问题，得出子问题的解后得到目标大问题的解。动态规划相当于地狱难度的递推。

2. 序列 dp 解法

序列型动态规划分为几种常见的问题：

取连续的子段（串）
- dp[i] 表示以 $i$ 为结尾
取子序列（不要求连续）
- dp[i] 表示以 $i$ 为结尾
- dp[i] 表示 $0\sim i$ 中 …
- dp[i] 长度为 $i$ 序列结尾的性质
分段
- dp[i] 表示以 $i$ 为结尾

二、例题

1. 最大子段和

题目描述

给出数组 $a$ ，如果我们取连续且非空的一段，那么这段的和最大是多少?

输入描述

第 $1$ 行，是一个正整数 $n$ ，数组 $a$ 的长度。
第 $2$ 行，用空格隔开的 $n$ 个整数，依次是 $a[1]\sim a[n]$ 的值。

输出描述

$1$ 个整数，为所求的最大的和

样例1

输入
6
1 -6 5 -4 2 4
输出
7

提示

【样例解释】
取 $5, - 4, 2, 4$ 可以得到最大的和 $7$ 。
【数据范围】
对于 $60\%$ 的数据， $n \leq 100$ 。
对于 $80\%$ 的数据， $n \leq 5000$ 。
对于 $100\%$ 的数据， $n \leq 100000$ 。

【问题类型】 取子段
【问题解法】 dp[i] 表示以 a[i] 为结尾的最大子段和是多少
【模板技巧】 如果前面都是负数，我不跟它们同流合污（a[i]）；如果前面大的，那就加入它们，做一个更大的数（dp[i-1]+a[i]）
【参考答案】

#include<bits/stdc++.h>
using namespace std;
int n,maxn=-1e8;
int a[100005];
int dp[100005];
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];dp[1]=a[1];for(int i=2;i<=n;i++){dp[i]=max(a[i],dp[i-1]+a[i]);maxn=max(maxn,dp[i]);}cout<<maxn;return 0;
}

2. 删数最大子段和（数据强度：pro max）

给出一个数组 a[]，删除一个元素后，求它的最大子段和。（子段是指数组中连续的一段元素）删除的元素可以由你自由选择，但是不能不删除任何元素，输出你能得到的最大的子段和。

思路：要删掉 a[i] 的时候会产生两个切口，第一个是以 a[i-1] 为结尾，第二个是以 a[i+1] 为开头。以 a[i-1] 为结尾取一个非常大的子段，以 a[i+1] 为开头取一个非常大的子段，将它们组合在一起，就可以完成本题。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e6+8;
const int NEGINF=-1e18;
int n,ans=NEGINF;
int a[MAXN],dpl[MAXN],dpr[MAXN];
/*
* dpl[i]:以i为右端点的最大子段和
* dpr[i]:以i为左端点的最大子段和
*/
signed main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)dpl[i]=max(dpl[i-1]+a[i],a[i]);for(int i=n;i>=1;i--)dpr[i]=max(dpr[i+1]+a[i],a[i]);for(int i=1;i<=n;i++)ans=max({ans,dpl[i-1],dpr[i+1],dpl[i-1]+dpr[i+1]});//选择左边/右边/左边和右边cout<<ans;return 0;
}

3. 最长上升子序列（数据强度：pro max）

求出数组 a[] 的最长上升子序列⻓度。

参考答案：

#include<bits/stdc++.h>
using namespace std;
int n,sz;
int a[5005];
int dp[5005];
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){if(sz==0||a[i]>dp[sz])sz++,dp[sz]=a[i];else{int p=lower_bound(dp+1,dp+sz+1,a[i])-dp;dp[p]=a[i];}}cout<<sz;return 0;
}

4. 3 或 5 的倍数序列

给出一个序列 a[]，要求你从中找出一个子序列，满足子序列中任意相邻两数之和是 $3$ 或 $5$ 的倍数。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e3+8;
const int MOD=1e9+7;
int n,a[MAXN],dp[MAXN];
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int ans=0;for(int i=1;i<=n;i++){for(int j=1;j<i;j++)if((a[i]+a[j])%3==0||(a[i]+a[j])%5==0)dp[i]=(dp[i]+dp[j]+1)%MOD;ans=(ans+dp[i])%MOD;}cout<<ans;return 0;
}

5. 数码约数序列

给出一个序列 a[]，要求你从中找出一个子序列，满足子序列中任意相邻两数，前一个数的末位数码是后一个数的首位数码的约数。
例如 $302, 817, 739000$ 是一个满足要求的序列，因为 $302$ 的末位 $2$ 是 $807$ 的首位 $8$ 的约数； $817$ 的末位 $7$ 是 $739000$ 的首位 $7$ 的约数。但是 $70, 1$ 就不满足要求，因为 $0$ 不是 $1$ 的约数。
问所有满足要求的子序列中，总和最大的序列的和是多少？（单独一个数也算满足要求的序列）

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+8;
long long n,dp[MAXN][10];
int main(){cin>>n;for(int i=1,a,fst,lst;i<=n;i++){cin>>a,fst=a,lst=a%10;while(fst>=10)fst/=10;for(int j=0;j<=9;j++)dp[i][j]=dp[i-1][j];for(int j=1;j<=fst;j++)if(fst%j==0)dp[i][lst]=max(dp[i][lst],dp[i-1][j]+a);}long long ans=0;for(int i=0;i<=9;i++)ans=max(ans,dp[n][i]);cout<<ans;return 0;
}

C++知识点总结(58)：序列型动态规划

动态规划Ⅰ 一、基础1. 意义2. 序列 dp 解法二、例题1. 最大子段和2. 删数最大子段和（数据强度：pro max）3. 最长上升子序列（数据强度：pro max）4. 3 或 5 的倍数序列5. 数码约数序列一、基础 1. 意义动…...

编程日记 2025/7/27 20:06:39

【系统架构设计师】真题论文: 论网络安全体系设计（包括解题思路和素材）

更多内容请见：备考系统架构设计师-专栏介绍和目录文章目录真题题目（2014年试题4）解题思路论文素材参考网络安全体系设计目标与原则网络安全体系的主要组成部分网络安全体系设计流程真题题目（2014年试题4）随着社会信息化的普及，计算机网络已经在各行各业得到了广泛…...

编程日记 2025/7/27 19:57:07

TypeScript学习笔记(三)

类型详细介绍七、常用类型与语法 1.any any 的含义是：任意类型，一旦将变量类型限制为 any , 那就意味着放弃了对该变量的类型检查。 // 明确的表示a的类型是 any —— 【显式的any】 let a: any // 以下对a的赋值，均⽆警告 a 100 a 你…...

编程日记 2025/7/27 11:28:30

logstash 解析数组格式json数据：split, json

1，需求说明原始数据格式： 1条 （2*2）》4个指标数据 [{"app":"aa","url":"www.1.com","metrics":[{"name":"cpu","value":11},{"name&quo…...

编程日记 2025/7/27 19:54:07

修改一下达梦disql 提示符

经常用disql的有时某些信息希望提示一下，默认的只显示SQL> 为了方便使用，可以在 glogin.sql 中增加些内容。 vi $DM_HOME/bin/disql_conf/glogin.sql增加以下几行 set time on set lineshow offcol global_name new_value global_name SELECT ins…...

编程日记 2025/7/26 17:35:52

Vue通用组件设计原则

在 Vue.js 开发中，设计通用组件是一项重要的任务，可以提升代码的复用性和可维护性。以下是通用组件设计的主要原则和最佳实践： 1. 清晰的职责划分通用组件应该具有单一的职责，专注于完成某一类特定功能，而不依赖具体…...

编程日记 2025/7/27 19:56:28

uniapp页面样式和布局和nvue教程详解

uniapp页面样式和布局和nvue教程尺寸单位 uni-app 支持的通用 css 单位包括 px、rpx px 即屏幕像素。rpx 即响应式px，一种根据屏幕宽度自适应的动态单位。以750宽的屏幕为基准，750rpx恰好为屏幕宽度。屏幕变宽，rpx 实际显示效果会等比放大…...

编程日记 2025/7/23 22:12:54

Ubuntu问题 -- 设置ubuntu的IP为静态IP (图形化界面设置) 小白友好

目的为了将ubuntu服务器IP固定, 方便ssh连接人在服务器前使用图形化界面设置设置找到自己的网卡名称, 我的是 eno1, 并进入设置界面查看当前的IP, 网关, 掩码和DNS (注意对应eno1) nmcli dev show掩码可以通过以下命令查看完整的 (注意对应eno1) , 我这里是255.255.255.…...

编程日记 2025/7/26 19:08:52

【Java】期末复习章节未完待续(版)

文章目录【01算法类】1.1 使用冒泡排序算法对数组a{9, 7, 4, 6, 3, 1,10}，按由小到大的规律排序数组中的元素。1.2 从键盘输入一个4位整数n，判断n是否是回文数。（回文数是指，将其数字反转排列的数与其本身相同。例如：…...

编程日记 2025/7/27 19:58:47

C语言数据结构——详细讲解双链表

从单链表到双链表：数据结构的演进与优化前言一、单链表回顾二、单链表的局限性三、什么是双链表四、双链表的优势1.双向遍历2.不带头双链表的用途3.带头双链表的用途五、双链表的操作双链表的插入操作（一）双链表的尾插操作（二&a…...

编程日记 2025/7/27 20:02:30

经验笔记：Git 中的远程仓库链接及上下游关系管理

Git 中的远程仓库链接及上下游关系管理 1. 远程仓库的链接信息当你克隆一个远程仓库时，Git 会在本地仓库中记录远程仓库的信息。这些信息包括远程仓库的 URL、默认的远程名称（通常是 origin），以及远程仓库中的所有分支和标签。…...

编程日记 2025/7/26 12:09:41

Swift闭包的本质

1 闭包的本质其实是一个引用类型：存储在堆空间上，由堆分配空间，且生命周期由ARC（自动引用计数机制）管理 2 捕获值：闭包会捕获上下文使用到的变量（引用类型会保持引用关系）&#xff…...

编程日记 2025/7/24 3:42:09

【SKFramework框架核心模块】3-2、音频管理模块

推荐阅读 CSDN主页GitHub开源地址Unity3D插件分享QQ群：398291828小红书小破站大家好，我是佛系工程师☆恬静的小魔龙☆，不定时更新Unity开发技巧，觉得有用记得一键三连哦。一、前言【Unity3D框架】SKFramework框架完全教程《全…...

编程日记 2025/7/26 14:00:50

常用Rust日志处理工具教程

在本文中，我想讨论Rust中的日志。通过一些背景信息，我将带您了解两个日志库：env_logger和log4rs。最后，我将分享我的建议和github的片段。 Rust log介绍 log包是Rust中日志API的事实标准，共有五个日志级别&#xff1…...

编程日记 2025/7/27 19:50:56

深入理解索引（二）

1.引言在数据库和数据结构中，索引（Index）是一种用于提高数据检索速度的重要机制。本文将详细深入介绍索引。 2. 为什么要使用索引大家在使用索引之前一定要搞清楚使用索引的目的，因为索引的不当使用可能不但起不到正向作用&a…...

编程日记 2025/7/26 22:04:08

Python 开发工具 -- PyCharm 简介

一、PyCharm 简介 PyCharm 是由 JetBrains 打造的一款 Python IDE。 PyCharm 具备一般 Python IDE 的功能，比如：调试、语法高亮、项目管理、代码跳转、智能提示、自动完成、单元测试、版本控制等。另外，PyCharm 还提供了一些很好的功能用…...

编程日记 2025/7/22 5:27:25

C# 属性学习理解记录

字段和属性左边字段，右边属性拓展，属性安全： 1、设置public private 和protected 等，只读，只写， 2、在get set 方法时，验证，异常时抛出错误...

编程日记 2025/6/29 1:19:51

使用chrome 访问虚拟机Apache2 的默认页面，出现了ERR_ADDRESS_UNREACHABLE这个鸟问题

本地环境主机MacOs Sequoia 15.1虚拟机Parallels Desktop 20 for Mac Pro Edition 版本 20.0.1 (55659)虚拟机-操作系统Ubuntu 22.04 服务器版本最小安装开发环境编辑器编译器调试工具数据库http服务web开发防火墙Vim9Gcc13Gdb14Mysql8Apache2Php8.3Iptables 第一坑数…...

编程日记 2025/7/25 16:22:39

【大数据学习 | Spark-Core】Spark的分区器(HashPartitioner和RangePartitioner)

之前学过的kv类型上面的算子 groupby groupByKey reduceBykey sortBy sortByKey join[cogroup left inner right] shuffle的 mapValues keys values flatMapValues 普通算子，管道形式的算子 shuffle的过程是因为数据产生了打乱重分，分组、排序、join等…...

编程日记 2025/7/8 13:54:49

第六届国际科技创新学术交流大会（IAECST 2024）暨第四届物流系统与交通运输国际学术会议（LSTT 2024）

重要信息会议官网：www.lstt.org 大会时间：2024年12月6-8日大会地点：中国-广州大会简介第六届国际科技创新学术交流大会暨第四届物流系统与交通运输国际学术会议（LSTT 2024）将于2024年12月6-8日在广州举办&…...

编程日记 2025/7/26 19:08:32

看Threejs好玩示例，学习创新与技术(ogl)

本文标题可能看的你莫名奇妙，什么是ogl？ogl是一个新的三维引擎库，可以简单任务是非常简化的ThreeJS。下面图是它的一个示例，可见虽然它是一个麻雀，但五脏还是比较全的。 1、先说OGL OGL的代码非常简单，主要…...

编程日记 2025/7/26 11:11:01

读书笔记_《创华为.任正非传》_精华书摘

人生经历 43岁，开始创建华为爷爷:金华火腿乡间厨师父亲: 1910年生，北平民大经济系读书->职业学校任教->国民党兵工厂会计，组织读书会(读书会后来有很多人在新中国成立后成为高级干部。) 母亲: 高中毕业，乡村教师&#xf…...

编程日记 2025/7/21 9:04:41

4.4 MySQL 触发器（Trigger）

触发器是一种特殊的数据库对象，在特定事件（如INSERT、UPDATE或DELETE）触发时自动执行定义好的操作。它可以帮助我们实现更高效的数据管理和业务规则的约束。 1. 简介 1.1 什么是触发器触发器（Trigger）是由用户定义的…...

编程日记 2025/7/27 0:30:50

遗传算法（Genetic Algorithm, GA）

简介遗传算法（Genetic Algorithm, GA）是一种基于自然选择和遗传机制的优化算法，由 John Holland 于20世纪70年代提出。它是一种模拟生物进化过程的启发式搜索算法，被广泛应用于函数优化、机器学习、调度问题等领域。代码说明 …...

编程日记 2025/7/26 15:32:36

CentOS8.5.2111（7）完整的Apache综合实验

一、实验目标 1.掌握Linux系统中Apache服务器的安装与配置； 2.掌握个人主页、虚拟目录、基于用户和主机的访问控制及虚拟主机的实现方法。二、实验要求练习使用linux系统下WEB服务器的配置方法。三、实验背景重庆工程学院为筹备“重庆工程大学”特申请了c…...

编程日记 2025/7/26 23:12:28

flink学习（3）——方法的使用—对流的处理（map，flatMap，filter）

map 数据 86.149.9.216 10001 17/05/2015:10:05:30 GET /presentations/logstash-monitorama-2013/images/github-contributions.png 83.149.9.216 10002 17/05/2015:10:06:53 GET /presentations/logstash-monitorama-2013/css/print/paper.css 83.149.9.216 10002 17/05/20…...

编程日记 2025/7/25 4:49:43