【动态规划-线性dp】【蓝桥杯备考训练】:乌龟棋、最长上升子序列、最长公共子序列、松散子序列、最大上升子序列和【已更新完成】

目录

1、乌龟棋

2、最长上升子序列

3、最长公共子序列

4、松散子序列

5、最大上升子序列和


1、乌龟棋

小明过生日的时候,爸爸送给他一副乌龟棋当作礼物。

乌龟棋的棋盘只有一行,该行有 N 个格子,每个格子上一个分数(非负整数)。

棋盘第 1 格是唯一的起点,第 N 格是终点,游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中共有 M 张爬行卡片,分成 4 种不同的类型(M 张卡片中不一定包含所有 4 种类型的卡片),每种类型的卡片上分别标有 1、2、3、4 四个数字之一,表示使用这种卡片后,乌龟棋子将向前爬行相应的格子数。

游戏中,玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片,控制乌龟棋子前进相应的格子数,每张卡片只能使用一次。

游戏中,乌龟棋子自动获得起点格子的分数,并且在后续的爬行中每到达一个格子,就得到该格子相应的分数。

玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显,用不同的爬行卡片使用顺序会使得最终游戏的得分不同,小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在,告诉你棋盘上每个格子的分数和所有的爬行卡片,你能告诉小明,他最多能得到多少分吗?

输入格式

输入文件的每行中两个数之间用一个空格隔开。

第 1 行 2 个正整数 N 和 M,分别表示棋盘格子数和爬行卡片数。

第 2 行 N 个非负整数,a1,a2,……,aN其中 ai表示棋盘第 i 个格子上的分数。

第 3 行 M 个整数,b1,b2,……,bM表示 M 张爬行卡片上的数字。

输入数据保证到达终点时刚好用光 M 张爬行卡片。

输出格式

输出只有 1 行,包含 1 个整数,表示小明最多能得到的分数。

数据范围

1≤N≤350
1≤M≤120
0≤ai≤100
1≤bi≤4
每种爬行卡片的张数不会超过 40。

输入样例:
9 5
6 10 14 2 8 8 18 5 17
1 3 1 2 1
输出样例:
73
思路:

用四个维度表示四个卡片的消耗量,状态转移方程:

auto &v=f[b1][b2][b3][b4];可以减少代码量

					int t=a[b1+2*b2+3*b3+4*b4+1];auto &v=f[b1][b2][b3][b4];if(b1)v=max(v,f[b1-1][b2][b3][b4]+t);if(b2)v=max(v,f[b1][b2-1][b3][b4]+t);if(b3)v=max(v,f[b1][b2][b3-1][b4]+t);if(b4)v=max(v,f[b1][b2][b3][b4-1]+t);
代码:
#include<bits/stdc++.h>using namespace std;const int N=41;int a[360];int b[5];int n,m;int f[N][N][N][N];int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=m;i++){int t;scanf("%d",&t);b[t]++;//cout<<b[t];}for(int b1=0;b1<=b[1];b1++)for(int b2=0;b2<=b[2];b2++)for(int b3=0;b3<=b[3];b3++)for(int b4=0;b4<=b[4];b4++){f[b1][b2][b3][b4]=a[b1+2*b2+3*b3+4*b4+1];}for(int b1=0;b1<=b[1];b1++)for(int b2=0;b2<=b[2];b2++)for(int b3=0;b3<=b[3];b3++)for(int b4=0;b4<=b[4];b4++){int t=a[b1+2*b2+3*b3+4*b4+1];auto &v=f[b1][b2][b3][b4];if(b1)v=max(v,f[b1-1][b2][b3][b4]+t);if(b2)v=max(v,f[b1][b2-1][b3][b4]+t);if(b3)v=max(v,f[b1][b2][b3-1][b4]+t);if(b4)v=max(v,f[b1][b2][b3][b4-1]+t);}cout<<f[b[1]][b[2]][b[3]][b[4]];return 0;
}

2、最长上升子序列

给定一个长度为 N 的数列,求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 N。

第二行包含 N个整数,表示完整序列。

输出格式

输出一个整数,表示最大长度。

数据范围

1≤N≤1000,
−1e9≤数列中的数≤109

输入样例:
7
3 1 2 1 8 5 6
输出样例:
4
思路:

状态转移方程:

			if(a[j]<a[i])f[i]=max(f[i],f[j]+1);res=max(res,f[i]);
代码:
#include<bits/stdc++.h>using namespace std;const int N=1003;int a[N];int n;int f[N];//以i结尾的最长子序列数 int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]),f[i]=1;int res=-1;for(int i=1;i<=n;i++)for(int j=0;j<i;j++){if(a[j]<a[i])f[i]=max(f[i],f[j]+1);res=max(res,f[i]);} cout<<res;return 0;
}

3、最长公共子序列

给定两个长度分别为 N和 M 的字符串 A 和 B,求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数 N 和 M。

第二行包含一个长度为 N 的字符串,表示字符串 A。

第三行包含一个长度为 M 的字符串,表示字符串 B。

字符串均由小写字母构成。

输出格式

输出一个整数,表示最大长度。

数据范围

1≤N,M≤1000

输入样例:
4 5
acbd
abedc
输出样例:
3
思路:
状态转移方程:
f[i][j]=max(f[i-1][j],f[i][j-1]);//这两个都算过了 if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);res=max(res,f[i][j]);
代码:
#include<bits/stdc++.h>using namespace std;int n,m;const int N=1003;char a[N],b[N];int f[N][N]; int main()
{cin>>n>>m;int res=-1;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++)cin>>b[i];//for(int i=1;i<=m;i++)cout<<b[i];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]);//这两个都算过了 if(a[i]==b[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1);res=max(res,f[i][j]);}cout<<res;return 0; 
}

4、松散子序列

给定一个仅含小写字母的字符串 s,假设 s 的一个子序列 t 的第 i 个字符对应了原字符串中的第 pi 个字符。

我们定义 s 的一个松散子序列为:对于 i>1 总是有 pi − pi−1≥2。

设一个子序列的价值为其包含的每个字符的价值之和(a∼z 分别为 1∼26)。

求 s 的松散子序列中的最大价值。

输入格式

输入一行包含一个字符串 s。

输出格式

输出一行包含一个整数表示答案。

数据范围

对于 20% 的评测用例,|s|≤10;
对于 40% 的评测用例,|s|≤300;
对于 70% 的评测用例,|s|≤5000;
对于所有评测用例,1≤|s|≤1e6,字符串中仅包含小写字母。

输入样例:
azaazaz
输出样例:
78
思路:

状态转移方程:

		f[i]=max(f[i],f[i-1]);if(i-2>=0)f[i]=max(f[i],f[i-2]+(a[i]-'a'+1));
代码:
#include<bits/stdc++.h>using namespace std;const int N=1e6+10;char a[N];int f[N];int main()
{scanf("%s",a+1);//从1索引开始读取int n=strlen(a+1);for(int i=1;i<=n;i++){//cout<<a[i]<<" ";f[i]=a[i]-'a'+1;}//int res=-1;for(int i=1;i<=n;i++){f[i]=max(f[i],f[i-1]);if(i-2>=0)f[i]=max(f[i],f[i-2]+(a[i]-'a'+1));//cout<<f[i]<<endl;//res=max(res,f[i]);还可以再优化!} cout<<f[n];return 0;
}

5、最大上升子序列和

一个数的序列 bi,当 b1<b2<…<bS 的时候,我们称这个序列是上升的。

对于给定的一个序列(a1,a2,…,aN),我们可以得到一些上升的子序列(ai1,ai2,…,aiK),这里1≤i1<i2<…<iK≤N。

比如,对于序列(1,7,3,5,9,4,8),有它的一些上升子序列,如(1,7),(3,4,8)等等。

这些子序列中和最大为18,为子序列(1,3,5,9)的和。

你的任务,就是对于给定的序列,求出最大上升子序列和。

注意,最长的上升子序列的和不一定是最大的,比如序列(100,1,2,3)的最大上升子序列和为100,而最长上升子序列为(1,2,3)。

输入格式

输入的第一行是序列的长度N。

第二行给出序列中的N个整数,这些整数的取值范围都在0到10000(可能重复)。

输出格式

输出一个整数,表示最大上升子序列和。

数据范围

1≤N≤1000

输入样例:
7
1 7 3 5 9 4 8
输出样例:
18
思路:

状态转移方程:

			if(a[i]>a[j])f[i]=max(f[i],f[j]+a[i]);
代码:
#include<bits/stdc++.h>using namespace std;const int N=1003;int a[N];int f[N]; int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];f[i]=a[i];}int res=-1;for(int i=1;i<=n;i++)for(int j=0;j<i;j++){//f[i]=max(f[i],f[j]);错误的,虽然j比i小,a[j]不一定比a[i]小if(a[i]>a[j])f[i]=max(f[i],f[j]+a[i]);//cout<<f[i]<<" ";res=max(res,f[i]);}cout<<res;return 0;
}

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

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

相关文章

【Springboot开发】后端代码基础框架

前言&#xff1a;主要介绍最基础的springboot开发架构 目录 1. overall2. 配置文件2.1 YAML2.2 properties2.3 配置文件加载顺序2.4 多配置文件 3. 代码包3.1 infrastructure3.1.1 persistence 3.2 application3.2.1 dto3.2.2 converter3.2.3 service 3.3 api3.3.1 vo3.3.2 req…

Django交易商场

Hello&#xff0c;我是小恒不会java 最近学习django&#xff0c;写了一个demo,学到了不少东西。 我在GitHub上开源了&#xff0c;提示‘自行查看代码&#xff0c;维护&#xff0c;运行’。 最近有事&#xff0c;先发布代码了&#xff0c;我就随缘维护更新吧 介绍&#xff1a; 定…

Harmony鸿蒙南向驱动开发-MIPI CSI

CSI&#xff08;Camera Serial Interface&#xff09;是由MIPI联盟下Camera工作组指定的接口标准。CSI-2是MIPI CSI第二版&#xff0c;主要由应用层、协议层、物理层组成&#xff0c;最大支持4通道数据传输、单线传输速度高达1Gb/s。 物理层支持HS&#xff08;High Speed&…

随机过程-BS定理

随机偏微分方程相比普通偏微分方程具有额外的随机项&#xff0c;反映了其描述的现象具有随机性质

华为 2024 届校园招聘-硬件通⽤/单板开发——第一套(部分题目分享,完整版带答案,共十套)

华为 2024 届校园招聘-硬件通⽤/单板开发——第一套 部分题目分享&#xff0c;完整版带答案(有答案和解析&#xff0c;答案非官方&#xff0c;未仔细校正&#xff0c;仅供参考&#xff09;&#xff08;共十套&#xff09;获取&#xff08;WX:didadidadidida313&#xff0c;加我…

贪心算法|860.柠檬水找零

力扣题目链接 class Solution { public:bool lemonadeChange(vector<int>& bills) {int five 0, ten 0, twenty 0;for (int bill : bills) {// 情况一if (bill 5) five;// 情况二if (bill 10) {if (five < 0) return false;ten;five--;}// 情况三if (bill …

基于ubuntu22.04系统安装nvidia A100驱动与NVLink启用

1、官方仓库 针对驱动包下载认准nvidia官网 dpkg -i nvidia-driver-local-repo-ubuntu2204-550.54.15_1.0-1_amd64.deb apt update apt search nvidia-driver-5502、安装 根据步骤1apt search nvidia-driver-550查出版本&#xff1a;此驱动包封在nvidia-driver-local-repo-ub…

数字社会下的智慧公厕:构筑智慧城市的重要组成部分

智慧城市已经成为现代城市发展的趋势&#xff0c;而其中的数字化转型更是推动未来社会治理体系和治理能力现代化的必然要求。在智慧城市建设中&#xff0c;智慧公厕作为一种新形态的信息化公共厕所&#xff0c;扮演着重要角色。本文智慧公厕源头实力厂家广州中期科技有限公司&a…

设计模式(22):解释器模式

解释器 是一种不常用的设计模式用于描述如何构成一个简单的语言解释器&#xff0c;主要用于使用面向对象语言开发的解释器和解释器设计当我们需要开发一种新的语言时&#xff0c;可以考虑使用解释器模式尽量不要使用解释器模式&#xff0c;后期维护会有很大麻烦。在项目中&…

Python:如何对FY3D TSHS的数据集进行重投影并输出为TIFF文件以及批量镶嵌插值?

完整代码见 Github&#xff1a;https://github.com/ChaoQiezi/read_fy3d_tshs&#xff0c;由于代码中注释较为详细&#xff0c;因此博客中部分操作一笔带过。 01 FY3D的HDF转TIFF 1.1 数据集说明 FY3D TSHS数据集是二级产品(TSHS即MWTS/MWHS 融合大气温湿度廓线/稳定度指数/…

CSS-语法、选择器

&#x1f4da;详见 W3scholl&#xff0c;本篇只做快速思维索引。 概述 CSS 是一种描述 HTML 文档样式的语言。 有三种插入样式表的方法&#xff1a; 外部 CSS内部 CSS行内 CSS &#x1f4c5; 外部 CSS 外部样式表存储在.css文件中。HTML 页面必须在 head 部分的<link&g…

ORAN C平面 Section Extension 22

ORAN C平面Section扩展22用于ACK/NACK请求。除section type 7外&#xff0c;section扩展22可以用于从O-DU发送到O-RU的所有section type和section扩展。 对于一个section描述&#xff0c;O-DU可以使用section扩展22要求O-RU使用section type 8 C平面消息进行ACK/NACK反馈。关于…

React路由快速入门:Class组件和函数式组件的使用

1. 介绍 在开始学习React路由之前&#xff0c;先了解一下什么是React路由。React Router是一个为React应用程序提供声明式路由的库。它可以帮助您在应用程序中管理不同的URL&#xff0c;并在这些URL上呈现相应的组件。 2. 安装 要在React应用程序中使用React路由&#xff0c;…

华为汽车的“计算+通信”电子电气架构

文章目录 整车结构 硬件平台 软件平台 总结展望 整车EEA&#xff08;电子电气架构&#xff09;&#xff0c;按照博世提出的演进路径&#xff0c;大致可以划分为四个阶段&#xff1a;分布式模块阶段、区域控制阶段、中央计算阶段、云计算阶段。示例如下&#xff1a; 本文选取…

联想电脑开启虚拟化失败,开启虚拟化却提示还没有开启虚拟化

安装虚拟机的时候&#xff0c; 电脑要开启虚拟化&#xff0c; Intel VT&#xff0c; 去BIOS开启了&#xff0c; 但是依然报错&#xff0c;说虚拟化处于禁用状态。 解决方案&#xff1a; 去联想官方&#xff0c;下载BIOS更新包&#xff0c;更新BIOS。 更新文档&#xff1a; 联…

vue中使用axios获取不到响应头Content-Disposition的解决办法

项目中&#xff0c;后端返回的文件流; 前端需要拿到响应头里的Content-Disposition字段的值&#xff0c;从中获取文件名 在控制台Headers中可以看到相关的字段和文件名&#xff0c;但是在axios里面却获取不到 如果想要让客户端访问到相关信息&#xff0c;服务器不仅要在head…

【算法刷题】八大排序算法总结(冒泡、选择、插入、二分插入、归并、快速、希尔、堆排序)

文章目录 八大排序算法总结1.冒泡排序2.选择排序3.插入排序4.二分插入排序5.归并排序6.快速排序7.希尔排序8.堆排序 八大排序算法总结 排序排序方法平均情况最好情况最坏情况空间稳定性1冒泡排序O(n2)O(n)O(n2)O(1)稳定2选择排序O(n2)O(n2)O(n2)O(1)不稳定3插入排序O(n2)O(n)O…

XUbuntu22.04之Typora添加水印并输出pdf文件(二百二十七)

简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏:多媒体系统工程师系列【原创干货持续更新中……】🚀 优质视频课程:AAOS车载系统+AOSP…

30个Python操作小技巧

前言 1、列表推导 列表的元素可以在一行中进行方便的循环。 numbers [1, 2, 3, 4, 5, 6, 7, 8] even_numbers [number for number in numbers if number % 2 0] print(even_numbers)输出&#xff1a; 在这里插入代码片[1,3,5,7] 同时&#xff0c;也可以用在字典上。 d…

前端入门:极简登录网页的制作(未使用JavaScript制作互动逻辑)

必备工具&#xff1a;vscode Visual Studio Code - Code Editing. Redefined 目录 前言 准备 HTML源文件的编写&#xff08;构建&#xff09; head部分 body部分 网页背景设置 网页主体构建 CSS源文件的编写&#xff08;设计&#xff09; 结果展示 前言 博主稍稍自…