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

动态规划刷题记录(2)

今天的三个题目属于模板题,可能将来会遇见它们的变形应用。

1、最长上升子序列问题

 这道题目的关键就在于我们的状态定义,我们定义:f(i)表示长度为i的子序列的末尾最大值。意思就是,比如一个子序列为:1,4,5,那么按我们的集合定义就应该是:f(3) = 5。这样定义了话我们就可以很容易的解题,我们只需要从头到尾遍历数组,找到当前数大于的最小值,然后更新找到的f。举个例子,f(2) = 3 f(3) = 5,这时候我们当前数是4,那么我们就把4接到3之后,也就是f(3) = 4。这里其实用到了贪心的思想,我们让不同长度的末尾值尽可能小,这样最长长度一定会尽可能长。代码你可以直接暴力寻找,也可以二分查找都可以。

#include <iostream>//直接暴力using namespace std;const int N = 1010;
int f[N] ,a[N] ,n;int main()
{cin >> n;for (int i = 1 ;i <= n ;i ++) cin >> a[i];for (int i = 1 ;i <= n ;i ++){f[i] = 1;for (int j = 1 ;j <= i ;j ++){if (a[i] > a[j]) f[i] = max(f[i] ,f[j] + 1);}}int res = -1;for (int i = 1 ;i <= n ;i ++) res = max(res ,f[i]);cout << res;return 0;
}
#include <iostream>//二分
#include <cstdio>
#include <algorithm>
#include <cstring>using namespace std;#define N 100100int f[N] ,len ,a[N] ,n;int main()
{cin >> n;for (int i = 1 ;i <= n ; i++) cin >> a[i];f[0] = -2e9;for (int i = 1 ;i <= n ;i ++){int l = 0 ,r = len;while (l < r){int mid = (l + r + 1) / 2;if (a[i] > f[mid]) l = mid;elser = mid - 1;}len = max(len ,r + 1);f[r + 1] = a[i];}cout << len;return 0;
}

2、最长公共子序列

这个题目的dp思路是:定义一个集合f(i ,j)表示字符串A的前i个字符以及字符串B的前j个字符中最长公共字符串长度。状态划分就可以是:1、a[i] == b[j]时,f[i][j] = f[i - 1][j - 1] +1。2、a[i] != b[j]时,最大公共字符串一定在A的前i - 1个字符和B的前j个字符 或者说A的前i个字符和B的前j - 1个字符中,因此,f[i][j] = max(f[i - 1][j] ,f[i][j - 1])。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>using namespace std;#define N 1100int f[N][N] ,n ,m;
char a[N] ,b[N];int main()
{cin >> n >>m;scanf("%s" ,a + 1);scanf("%s" ,b + 1);f[0][0] = 0;for (int i = 1 ;i <= n ;i ++)for (int j = 1 ;j <= m ;j ++){if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;f[i][j] = max(f[i - 1][j] ,f[i][j]);f[i][j] = max(f[i][j - 1] ,f[i][j]);}cout << f[n][m];return 0;
}

3、最长公共上升子序列

 这道题的思路是前两道题的结合版本,更加的复杂,很难想到。f(i ,j)表示第一个序列前i个字母以及第二个序列前j个字母,并且以b[j]结尾的公共上升子序列的最大值。那么我们的状态划分就可以分为两大类:一、a[i] != b[j]的时候,最大公共上升序列跟a[i]无关,那么状态转移:f[i][j] = f[i - 1][j]。二、a[i] == b[j]的时候,最大公共上升序列的末尾就是a[i] ,那么我们就根据倒数第二个值是哪一个划分状态,f[i][j] = max(f[i - 1][1] ,f[i - 1][2] .......f[i - 1][j - 1])。根据这个思路我们写出代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>using namespace std;#define N 3500
#define ll long longll f[N][N] ,n ,a[N] ,b[N];int main()
{cin >> n;for (int i = 1 ;i <= n ;i ++) cin >> a[i];for (int j = 1 ;j <= n ;j ++) cin >> b[j];for (int i = 1 ;i <= n ;i ++){for (int j = 1 ;j <= n ;j ++){ll maxv = 1;//作为中间值存取f(i - 1 ,1 ~ j - 1)的最大值f[i][j] = f[i - 1][j];if (a[i] == b[j]){for (int k = 1 ;k < j ;k ++){if (a[i] > b[k]) maxv = max(maxv ,f[i - 1][k] + 1);//注意,必须a[i] > b[k]否则就不能满足递增序列的条件。}f[i][j] = max(f[i][j] ,maxv);}}}ll ans = -1e9;for (int i = 1 ;i <= n ; i ++) ans = max(ans ,f[n][i]);cout << ans;return 0;
}

 三重循环n方复杂度,很明显时间复杂度太高,我们考虑优化。根据代码我们可以看出,在i确定的情况下,f[i][k - 1]的值是跟j没有关系的,我们就可以优化掉第三层循环:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>using namespace std;#define N 3050int f[N][N] ,n ,a[N] ,b[N];int main()
{cin >> n;for (int i = 1 ;i <= n ;i ++) cin >> a[i];for (int j = 1 ;j <= n ;j ++) cin >> b[j];for (int i = 1 ;i <= n ;i ++){int maxv = 1;for (int j = 1 ;j <= n ;j ++){f[i][j] = f[i - 1][j];if (a[i] == b[j]) f[i][j] = max(f[i][j] ,maxv);if (a[i] > b[j])  maxv = max(maxv ,f[i - 1][j] + 1);}}int ans = 0;for (int i = 1 ;i <= n ; i ++) ans = max(ans ,f[n][i]);cout << ans;return 0;
}

 

 

相关文章:

动态规划刷题记录(2)

今天的三个题目属于模板题&#xff0c;可能将来会遇见它们的变形应用。 1、最长上升子序列问题 这道题目的关键就在于我们的状态定义&#xff0c;我们定义&#xff1a;f(i)表示长度为i的子序列的末尾最大值。意思就是&#xff0c;比如一个子序列为&#xff1a;1,4,5&#xff0…...

2023年广东省网络安全竞赛——Web 渗透测试解析(超级详细)

任务一:Web 渗透测试 任务环境说明: √ 服务器场景:Server03 √ 服务器场景操作系统:未知(关闭连接) 通过本地 PC 中的渗透测试平台 Kali 对靶机进行 WEB 渗透,找到页面内的文件上传漏洞并且尝试进行上传攻击,将文件上传成功后的页面回显字符串作为Flag 提交(如:…...

MI-SegNet阅读笔记

MI-SegNet: Mutual Information-Based US Segmentation for Unseen Domain Generalization 摘要 解决医学成像泛化能力提出了一种新的基于互信息(MI)的框架MI- segnet分离解剖结构和领域特征采用两个编码器提取相关特征&#xff1a;两个特征映射中出现的任何MI都将受到惩罚&a…...

十、MyBatis分页插件

1.分页插件实现的步骤 ①在pom.xml添加依赖 <dependency><groupId>com.github.pagehelper</groupId><artifactId>pagehelper</artifactId><version>5.2.0</version> </dependency>②配置分页插件 mybatis-config.xml 在MyB…...

EasyCVR平台国标GB28181协议设备接入时,可支持过滤通道类型

EasyCVR基于云边端智能协同架构&#xff0c;能支持海量视频的轻量化接入与集中汇聚管理&#xff0c;平台可支持多协议接入&#xff0c;包括市场主流标准协议与厂家私有协议及SDK&#xff0c;如&#xff1a;国标GB28181、RTMP、RTSP/Onvif、海康Ehome、海康SDK、宇视SDK等&#…...

玩转git的第1章节:git的理论以及操作规则

一 git原理 1.1 git的操作原理 上图是Git与提交有关的三个命令对应的操作&#xff1a; Add命令是把文件从IDE的工作目录添加到本地仓库的stage区&#xff0c; Commit命令把stage区的暂存文件提交到当前分支的仓库&#xff0c;并清空stage区。 Push命令把本地仓库的提交同步…...

【新2023Q2模拟题JAVA】华为OD机试 - 二叉树层次遍历

最近更新的博客 华为od 2023 | 什么是华为od,od 薪资待遇,od机试题清单华为OD机试真题大全,用 Python 解华为机试题 | 机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为od机试,独家整理 已参加机试人员的实战技巧本篇题解:二叉树层次遍历 题目 有一棵…...

轻松拿结果-第三部分 同欲 -第六章 有凝聚力才有战斗力

第三部分 同欲 “上下同欲者胜”,同结果、共承担,不仅是打造销售铁军军魂的必要条件,也能让成员们对每个结果负责,更好更快实现目标。 第六章 有凝聚力才有战斗力 管理者有担当才能上下齐心 苦劳是自己的,功劳是团队的 做管理者,就要做好承受苦劳奉献功劳的心理准备 学…...

chatGPT 会给程序员带来失业潮吗?

AIChatGPT根本不是取代普通人工作&#xff0c;让很多人失业那么简单。他现在直接革的是世界级巨头的命&#xff0c;你从他们的反应就能看出来这个人工智能将掀起一场怎样规模的战争&#xff0c;什么腾讯百度纷纷研发自己的版本&#xff0c;谷歌是直接拉响红色警报&#xff0c;那…...

Vue项目proxyTable跨域配置

Vue项目proxyTable跨域配置文章说明proxyTable跨域配置config / dev.env.jsconfig / prod.env.jsconfig / index.jsutils / request.js接口api.js路径转换解析文章说明 学习连接 - 重要❤ - 一文详解vue-cli2.0与vue-cli3.0之间的区别 1. vue cli 2.0项目2. 本地运行时&#x…...

ubuntu16.04搭建gitlab

ubuntu16.04搭建gitlab 目录ubuntu16.04搭建gitlab一、在虚拟机ubuntu16.04安装gitlab二、配置gitlab三、使用gitlab四、踩坑记录工作中遇到需要在远端服务器搭建gitlab&#xff0c;耗时4天&#xff0c;踩坑无数&#xff0c;特此开个虚拟机再次搭建一次gitlab并记录供以后参考&…...

SSMP综合案例

案例实现方案分析 实体类开发————使用Lombok快速制作实体类 Dao开发————整合MyBatisPlus&#xff0c;制作数据层测试类 Service开发————基于MyBatisPlus进行增量开发&#xff0c;制作业务层测试类 Controller开发————基于Restful开发&#xff0c;使用PostM…...

让你的作品更出色——词云Word Cloud的制作方法(基于python,WordCloud,stylecloud)

让你的作品更出色—— 词云Word Cloud的制作方法&#xff08;基于python) 本文目录&#xff1a; 一、词云的简介 二、 实现原理和流程 1、制作词云流程图 2、词云实现原理 三、 实现词云的方式 1、安装词云相关模块库 2、WordCloud库 3、stylecloud库 四、总结 一、词…...

axios请求拦截器

在vue项目中&#xff0c;通常使用axios与后台进行数据交互&#xff0c;axios是一款基于promise封装的库&#xff0c; axios特性&#xff1a; 1、axios 是一个基于promise的HTTP库&#xff0c;支持promise所有的API 2、浏览器端/node端&#xff08;服务器端&#xff09;都可以…...

四个常见的Linux技术面问题

刚毕业要找工作了&#xff0c;只要是你找工作就会有面试这个环节&#xff0c;那么在面试环节中&#xff0c;有哪些注意事项值得我的关注呢&#xff1f;特别是专业技术岗位&#xff0c;这样的岗位询问一般都是在职的工程师&#xff0c;如何在面试环节更好地理解面试官的问题&…...

有什么适合程序员查资料的网站

当今信息爆炸的时代&#xff0c;程序员每天需要花费大量的时间查找相关技术文档、知识和工具。但是&#xff0c;因为互联网上的内容如此之多&#xff0c;选择合适的网站可以成为一项艰巨的任务。在本文中&#xff0c;我们将介绍几个适合程序员查资料的网站&#xff0c;并详细阐…...

(七)手把手带你搭建精美简洁的个人时间管理网站—实现登录与注册的前端代码【源码】

&#x1f31f;所属专栏&#xff1a;献给榕榕 &#x1f414;作者简介&#xff1a;rchjr——五带信管菜只因一枚 &#x1f62e;前言&#xff1a;该专栏系为女友准备的&#xff0c;里面会不定时发一些讨好她的技术作品&#xff0c;感兴趣的小伙伴可以关注一下~&#x1f449;文章简…...

Day933.如何将设计最终落地到代码 -系统重构实战

如何将设计最终落地到代码 Hi&#xff0c;我是阿昌&#xff0c;今天学习记录的是关于如何将设计最终落地到代码的内容。 这要将各个组件拆分到独立的模块工程中&#xff0c;最终将架构设计落地到代码中。 组件化架构重构 5 个关键的步骤分别是&#xff1a; 设计守护解耦移动…...

209. 长度最小的子数组

209. 长度最小的子数组 力扣题目链接(opens new window) 给定一个含有 n 个正整数的数组和一个正整数 s &#xff0c;找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组&#xff0c;并返回其长度。如果不存在符合条件的子数组&#xff0c;返回 0。 示例&#xff1a; 输入…...

【数据结构与算法】查找(Search)【详解】

文章目录查找查找概论一、查找的基本概念顺序表查找一、定义二、算法有序表查找一、折半查找二、插值查找三、斐波那契查找线性索引查找一、稠密索引二、分块索引三、倒排索引二叉树排序与平衡二叉树一、二叉排序树1、定义2、二叉排序树的常见操作3、性能分析二、平衡二叉树1、…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

ubuntu搭建nfs服务centos挂载访问

在Ubuntu上设置NFS服务器 在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享&#xff0c;例如/shared&#xff1a; sudo mkdir /shared sud…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...