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

【算法】dp题单

题单链接: https://vjudge.net/contest/574209#overview

目录

1. 洛谷 P1020 导弹拦截 (dp+二分+Dilworth 定理)

2. P1439 最长公共子序列(二分求最长公共子序列)

3. 洛谷 P1854 花店橱窗布置 (线性dp + 用pre数组记录路径) 


1. 洛谷 P1020 导弹拦截 (dp+二分+Dilworth 定理)

题目:  https://www.luogu.com.cn/problem/P1020

思想:第一问是求最长不上升子序列,即后一项小于等于前一项,由于数据1e5,考虑二分。

首先把当前项小于等于前一项的加入 f 数组,如果当前项大于 f 数组前一项,那么向前找 f 数组的第一项小于当前项的下标,并用当前值代替二分找到的这个数。

第二问是求不上升子序列的个数,根据Dilworth 定理,一个序列若干个单调不升子序列的最小个数等于该序列最长上升子序列的个数,可以知这题求最长上升子序列的个数。首先把当前值大于 f 数组前一项的值加入 f 数组。如果小等于,那么找到 f 数组第一个大于等于当前值的项(为什么是大于等于,而不是大于,因为最长上升子序列要满足严格大于,所以等于的情况也需要被替代),并用当前值代替二分找到的这个值。

考虑一个数列5 2 3 1 4

首先,把5加入答案序列中,然后加2,发现2<5所以显然2替换5不会使结果更差,

那么答案序列就是{2},然后加3,发现3>2,所以直接把3加到答案序列中:{2,3}

然后加1,我们发现1<3,于是我们找到一个最小的但是比1大的数字2,然后把1替换2,为什么这么做不会影响结果呢?你可以这么想,我们当前已经求出了一个当前最优的序列,如果我们用1替换2,然后后面来一个数字替换了3,那么我们就可以得到一个更优的序列,而如果没有数字替换3,那么这个1替换2也就是没有贡献的,不会影响我们结果的最优性。至于,如何找到一个最小的但是大于某个数字的数字,弄个二分查找就行了,因为我们的答案序列是有序的呀。

代码:

// Problem: B - 导弹拦截
// Contest: Virtual Judge - CQJTU-DP题单1——线性DP
// URL: https://vjudge.net/contest/574209#problem/B
// Memory Limit: 131 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;typedef long long ll;const int N = 2e5+5;
const int inf = 0x3f3f3f3f;int a[N];
int f[N];int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int x=0;int n=0;while(cin>>x){   a[++n]=x;}memset(f,0,sizeof(f));f[0]=1e9;  int cnt=0;  for(int i=1;i<=n;i++){if(a[i]<=f[cnt]){   //得到不递增的数组f[++cnt]=a[i];  }else{  int l=1,r=cnt;  //找到第一个小于当前导弹高度的元素位置,将其更新为导弹高度while(l<r){int mid=(l+r)/2;if(f[mid]<a[i]){r=mid;}else l=mid+1;}f[l]=a[i];}/*for(int i=1;i<=cnt;i++){cout<<f[i]<<' ';}cout<<"\n";*/}cout<<cnt<<"\n";cnt=0;memset(f,0,sizeof(f));for(int i=1;i<=n;i++){if(a[i]>f[cnt]){  //找到递增数组f[++cnt]=a[i];}else{int l=1,r=cnt;while(l<r){  //找到第一个大于等于当前导弹高度的导弹位置,将其更新为导弹高度int mid=(l+r)/2;if(f[mid]>=a[i]){r=mid;}else l=mid+1;}f[l]=a[i];}/*for(int i=1;i<=cnt;i++){cout<<f[i]<<' ';}cout<<"\n";*/}cout<<cnt<<"\n";return 0;	}

 

2. P1439 最长公共子序列(二分求最长公共子序列)

 题目:  https://www.luogu.com.cn/problem/P1439

思想:

首先,我们可以想到,最长公共子序列,就是两段所含数字完全一样,并且数字的顺序也是完全一样的序列。

而顺序,我们可以想到类似哈希的思想,考虑建立一个类似map的关系数组f[ai]=i,那么我们找到的序列只要是上升的,顺序就是一样的,然后考虑数字完全一样,由于我们已经有了一个f[ai]=i,所以我们把对应的bi改成f[bi],就可以确保数字相等了呀!

这时,就是在f[bi]的数组中求个最长上升子序列了,二分搞一搞就好了。STL大法好!

代码:

// Problem: C - 最长公共子序列
// Contest: Virtual Judge - CQJTU-DP题单1——线性DP
// URL: https://vjudge.net/contest/574209#problem/C
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;typedef long long ll;const int N = 2e5+5;
const int inf = 0x3f3f3f3f;int n;
int a[N],b[N];
int f[N];int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n;map<int,int> mp;for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]=i;}for(int i=1;i<=n;i++){cin>>b[i];//cout<<mp[b[i]]<<' ';}//cout<<"\n";//mp[b[i]]可以表示a数组中的每个数在b中的位置保证数字一样//然后找最长上升子序列保证顺序一样memset(f,127,sizeof(f));f[0]=0;int cnt=0;for(int i=1;i<=n;i++){if(mp[b[i]]>f[cnt]){  //找到b数组的最长上升子序列f[++cnt]=mp[b[i]];}else{int l=0,r=cnt;while(l<r){int mid=(l+r)/2;if(f[mid]>mp[b[i]]){r=mid;}else l=mid+1;}f[l]=min(mp[b[i]],f[l]);}/*for(int i=1;i<=cnt;i++){cout<<mp[i]<<' ';}cout<<"\n";*/}cout<<cnt<<"\n";return 0;	}

 

3. 洛谷 P1854 花店橱窗布置 (线性dp + 用pre数组记录路径) 

 题目:  https://www.luogu.com.cn/problem/P1854

思想:用 k 遍历 j 找到这一行最大的值,并且用 pre 数组记录当前点前一个位置为 k ,即上一行最大值的位置,结果最大值需要遍历最后一行每一列的值,而不是 f[n][m],然后以这个点往前找

pre数组 ,用pos数组存下每一行的值,最后输出。 pos[i-1] = pre[i][pos[i]]

代码:

// Problem: E - 花店橱窗布置
// Contest: Virtual Judge - CQJTU-DP题单1——线性DP
// URL: https://vjudge.net/contest/574209#problem/E
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;typedef long long ll;const int N = 1001;
const int inf = 0x3f3f3f3f;int n,m;
int a[N][N];
int f[N][N];
int pre[N][N];
int pos[N];int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){f[i][j]=-inf;}}memset(pre,0,sizeof(pre));/*for(int i=1;i<=n;i++){f[0][i]=0;}*/for(int i=1;i<=n;i++){f[0][i]=0;for(int j=i;j<=m;j++){for(int k=i-1;k<j;k++){if(f[i-1][k]+a[i][j]>f[i][j]){f[i][j]=f[i-1][k]+a[i][j];pre[i][j]=k;}}}}int maxv=-inf;for(int i=1;i<=m;i++){if(f[n][i]>maxv){pos[n]=i;maxv=f[n][i];}}cout<<maxv<<"\n";for(int i=n;pre[i][pos[i]]!=0;i--){pos[i-1]=pre[i][pos[i]];}for(int i=1;i<=n;i++){cout<<pos[i]<<' ';}cout<<"\n";return 0;	}

相关文章:

【算法】dp题单

题单链接&#xff1a; https://vjudge.net/contest/574209#overview 目录 1. 洛谷 P1020 导弹拦截 &#xff08;dp二分Dilworth 定理&#xff09; 2. P1439 最长公共子序列&#xff08;二分求最长公共子序列&#xff09; 3. 洛谷 P1854 花店橱窗布置 &#xff08;线性dp 用…...

Verilog视频信号图形显示 FPGA(iCE40)

您需要一块带视频输出的 FPGA 板。 我们将在 640x480 下工作&#xff0c;几乎任何视频输出都可以在此像素工作。 它有助于轻松地对 FPGA 板进行编程并相当熟悉 Verilog。 如果您没有开发板&#xff0c;请不要担心&#xff0c;您可以使用 Verilator 模拟器。 材料 Lattice iCE…...

【LeetCode 面试经典150题】26. Remove Duplicates from Sorted Array 在有序数组中移除重复元素

26. Remove Duplicates from Sorted Array 题目大意 Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then …...

linux系统下sql脚本的执行与导出

terminal中执行 执行 mysql -u [username] -p -D [databasename] < [XXX.sql] 导出 mysql -u [username] -p [datbasename] > [XXX.sql] 导出的数据库名自定义。 mysql -u [username] -p [databasename] [tablename] > [xxx.sql] 导出表名自定义 mysql shell 执行 …...

MyBatis学习一:快速入门

前言 公司要求没办法&#xff0c;前端也要了解一下后端知识&#xff0c;这里记录一下自己的学习 学习教程&#xff1a;黑马mybatis教程全套视频教程&#xff0c;2天Mybatis框架从入门到精通 文档&#xff1a; https://mybatis.net.cn/index.html MyBatis 快速入门&#xf…...

零售业物流这个防漏水技术,居然没有翻车!

随着科技的不断发展&#xff0c;水浸监控系统在各个领域得到了广泛应用。水浸监控不仅仅是为了保护建筑结构和设备&#xff0c;更是为了防范因水灾引起的生命安全和财产损失。 因此&#xff0c;为了有效预防和应对水浸事件&#xff0c;水浸监控系统应运而生&#xff0c;成为各行…...

主浏览器优化之路1——你现在在用的是什么浏览器?Edge?谷歌?火狐?360!?

上一世&#xff0c;我的浏览器之路 引言为什么要用两个浏览器为什么一定要放弃火狐结尾给大家一个猜数字小游戏&#xff08;测运气&#xff09; 引言 小时候&#xff0c;我一开始上网的浏览器是2345王牌浏览器吧&#xff0c; 因为上面集成了很多网站&#xff0c;我记得上面有7…...

gitlab请求合并分支

直接去看原文: 原文链接:Gitlab合并请求相关流程_source branch target branch-CSDN博客 --------------------------------------------------------------------------------------------------------------------------------- 入口&#xff1a; 仓库控制台的这两个地方都…...

使用Vue3开发学生管理系统模板1

环境搭建 通过解压之前《Vue3开发后台管理系统模板》的代码&#xff0c;我们能够得到用户增删改查的页面&#xff0c;我们基于用户增删改查的页面做进一步的优化。 创建学生增删改查页面 第一步&#xff1a;复制用户增删改查页面&#xff0c;重命名为StudentCRUD.vue <…...

【cmake实战:番外】交叉编译——Linaro

【cmake实战&#xff1a;番外】交叉编译——Linaro 一、交叉编译1、交叉编译简介2、为什么会有交叉编译 二、交叉编译链1、什么是交叉编译链2、交叉编译工具 三、Linaro1、下载2、解压3、demo3.1、toolchain_aarch64.cmake3.2、CMakeLists.txt3.3、main.cpp 4、执行编译5、查看…...

2024年年初Java5年实战面试题(北京)

高阶篇&#xff1a; 一、在面对千万条并发请求的情况下&#xff0c;如果数据库频繁查询导致崩溃&#xff0c;可以采取以下措施来解决问题: 1.缓存数据:可以使用缓存技术来减少对数据库的查询次数。将经常查询的数据存储在缓存中&#xff0c;例如使用Redis等内存数据库&#xff…...

【Apache-2.0】springboot-openai-chatgpt超级AI大脑产品架构图

springboot-openai-chatgpt: 一个基于SpringCloud的Chatgpt机器人&#xff0c;已对接GPT-3.5、GPT-4.0、百度文心一言、stable diffusion AI绘图、Midjourney绘图。用户可以在界面上与聊天机器人进行对话&#xff0c;聊天机器人会根据用户的输入自动生成回复。同时也支持画图&a…...

如何在iPhone设备中查看崩溃日志

​ 目录 如何在iPhone设备中查看崩溃日志 摘要 引言 导致iPhone设备崩溃的主要原因是什么&#xff1f; 使用克魔助手查看iPhone设备中的崩溃日志 奔溃日志分析 总结 摘要 本文介绍了如何在iPhone设备中查看崩溃日志&#xff0c;以便调查崩溃的原因。我们将展示三种不同的…...

对接第三方接口鉴权(Spring Boot+Aop+注解实现Api接口签名验证)

前言 一个web系统&#xff0c;从接口的使用范围也可以分为对内和对外两种&#xff0c;对内的接口主要限于一些我们内部系统的调用&#xff0c;多是通过内网进行调用&#xff0c;往往不用考虑太复杂的鉴权操作。但是&#xff0c;对于对外的接口&#xff0c;我们就不得不重视这个…...

微服务-理论(CAP,一致性协议)

CAP理论 关于CAP理论的介绍可以直接看这篇文章 CAP分别是什么&#xff1f; 一致性&#xff08;Consistency 一致性包括强一致性&#xff0c;弱一致性&#xff0c;最终一致性。 一致性其实是指数据的一致性&#xff0c;为什么数据会不一致呢&#xff1f; 如上面这张图&…...

CTFshow web入门web128-php特性31

开启环境: 一个新的姿势&#xff0c;当php扩展目录下有php_gettext.dll时&#xff1a; _()是一个函数。 _()gettext() 是gettext()的拓展函数&#xff0c;开启text扩展get_defined_vars — 返回由所有已定义变量所组成的数组。 call_user_func — 把第一个参数作为回调函数调…...

再见2023,你好2024(附新年烟花python实现)

亲爱的朋友们&#xff1a; 写点什么呢&#xff0c;我已经停更两个月了。2023年快结束了&#xff0c;时间真的过得好快&#xff0c;总要写点什么留下纪念吧。这一年伴随着许多挑战和机会&#xff0c;给了我无数的成长和体验。坦白说&#xff0c;有时候我觉得自己好像是在时间的…...

Redis 的常用命令

一、Redis 通用命令 TYPE key&#xff1a;返回 key 所储存的值的类型。 OBJECT ENCODING key&#xff1a;返回key所储存的值的底层编码方式。 DEL key&#xff1a;该命令用于在 key 存在时删除 key。 EXPIRE key seconds&#xff1a;设置指定key的过期时间。 RENAME key newke…...

【模拟电路】模拟集成电路之神-NE555

一、集成电路NE555简介 二、功能框图与引脚说明 三、比较器&#xff08;运放&#xff09; 四、反相门&#xff08;非门&#xff09; 五、或非门 六、双稳态触发器 七、NE555的工作原理 集成电路NE555的芯片手册 C5157696 一、集成电路NE555简介 NE555起源于上个世纪70年代&a…...

收集最新的 Sci-Hub 网址(本文章持续更新2024)

自用收集最新的 Sci-Hub 网址 本文章持续更新收集 Sci-Hub 的可用网址链接仅供交流学习使用&#xff0c;如对您有所帮助&#xff0c;请收藏并推荐给需要的朋友&#xff0c;由于网站限制&#xff0c;不一定所有网址都能在您所在的位置访问&#xff0c;通常情况下&#xff0c;一…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...