-
2022-03-06 13:13:35
【题目描述】
设有由n(1≤n≤200)个不相同的整数组成的数列,记为:b(1)、b(2)、……、b(n)若存在i1<i2<i3<…<ie 且有b(i1)<=b(i2)<=…<=b(ie)则称为长度为e的不下降序列。程序要求,当原数列出之后,求出最长的不下降序列。
例如
13,7,9,16,38,24,37,18,44,19,21,22,63,15
。例中13,16,18,19,21,22,63
就是一个长度为7的不下降序列,同时也有7 ,9,16,18,19,21,22,63
组成的长度为8的不下降序列。【输入】
第一行为n,第二行为用空格隔开的n个整数。
【输出】
第一行为输出最大个数max(形式见样例);
第二行为max个整数形成的不下降序列,答案可能不唯一,输出一种就可以了,本题进行特殊评测。
【输入样例】
14 13 7 9 16 38 24 37 18 44 19 21 22 63 15
【输出样例】
max=8 7 9 16 18 19 21 22 63
算法解析
可以从后往前进行枚举(从前往后也行),在b[i]后面找到比b[i]大的最长上升子序列起始点b[j]并记录,再更新数组
代码如下
#include<bits/stdc++.h> using namespace std; int b[200][10],n,l,k; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>b[i][1];//数值 b[i][2]=1;//长度 b[i][3]=0;//前驱 } for(int i=n-1;i>=1;i--) { l=k=0; for(int j=i+1;j<=n;j++) if(b[j][1]>=b[i][1]&&b[j][2]>l) { l=b[j][2]; k=j; } if(l>0) { b[i][2]+=l; b[i][3]=k; } } k=0; for(int i=1;i<=n;i++) if(b[i][2]>b[k][2]) k=i; cout<<"max="<<b[k][2]<<endl; for(int i=k;i!=0;i=b[i][3]) cout<<b[i][1]<<' '; return 0; }
更多相关内容 -
动态规划之最长不下降子序列
2021-08-11 12:30:26一、概念明确 先来看一串数字:(20,17,19,22,4,7,10,12,5,2,13) 1.序列:像以上排成一列的数字,我们叫它序列,其中每个数字,可以被称为一个元素。...3.不下降子序列:不下降的意思是上升或者相...一、概念明确
先来看一串数字:(20,17,19,22,4,7,10,12,5,2,13)
1.序列:像以上排成一列的数字,我们叫它序列,其中每个数字,可以被称为一个元素。
2.子序列:将序列中的部分元素或者全部元素取出后构成的一个新序列,我们称为子序列。
例:将元素 17,22,6,7 取出来构成一个新序列 (17,22,6,7),那么它就是一个子序列
注意:子序列是有序的,不能将后面的元素写在前面。比如写成(22,17,6,7)这种。
3.不下降子序列:不下降的意思是上升或者相同。
例:将元素 17,19,22取出来构成一个新序列 (17,19,22),这个序列中的每个元素均大于或等于前一个元素,22大于19,19大于17,因此,我们称这个序列为不下降子序列。再如将元素6,7,10,12,13取出来构成一个新序列(6,7,10,12,13),此序列符合不下降子序列的定义,因此它也是一个不下降子序列
4.最长不下降子序列: 子序列有很多,求出最长不下降子序列的意思是要求出一个子序列,它是不下降的,并且它在所有不下降的子序列中元素最多,这个最长不下降子序列可能有多个。
例:将元素6,7,10,12,13取出来构成一个新序列(6,7,10,12,13),此时它就是一个最长不下降子序列,长度为5。虽然(10,12,13)、(17,19,22)、(2,13)、(5,13)等等都是不下降子序列,但是它们的长度都不是最长的,因此不能称为最长不下降子序列。
二、解题方法
可以利用动态规划进行解题。在利用动态规划进行解题的时候,可以进一步划分为两种思路,分别是从前往后推理和从后往前推理。这两种思路都能够求出最长不下降子序列。
1.从前往后推理:依序求出以原序列中各元素分别为子序列结尾情况下能得出的最长不下降子序列
例子:以序列 (11,15,12,13,5,2)为例,通过从前往后推理求出最长不下降子序列的长度
以1号元素为子序列的结尾:此时最长不下降子序列长度为1,因为只有1号元素本身(11)
以2号元素为子序列的结尾:此时最长不下降子序列长度为2,此时包含1号元素和2号元素(11,15)
以3号元素为子序列的结尾:此时最长不下降子序列长度为2,此时包含1号元素和3号元素(11,12)
以4号元素为子序列的结尾:此时最长不下降子序列长度为3,此时包含1、3、4号元素(11,12,13)
以5号元素为子序列的结尾:此时最长不下降子序列长度为1,此时包含5号元素本身(5)
以6号元素为子序列的结尾:此时最长不下降子序列长度为1,此时包含6号元素本身(2)
如下图所示:
2.从后往前推理:依序求出以原序列中各元素分别为子序列起点情况下能得出的最长不下降子序列
以6号元素为子序列的起点:此时最长不下降子序列长度为1,因为只有6号元素本身(2)
以5号元素为子序列的起点:因为以5为起点,后面没有大于等于它的数字,此时最长不下降子序列长度为1,因为只有5号元素本身(5)
以4号元素为子序列的起点:因为以13为起点,后面没有大于等于它的数字,此时最长不下降子序列长度为1,因为只有4号元素本身(13)
以3号元素为子序列的起点:此时最长不下降子序列长度为2,此时包含3、4号元素(12,13)
以2号元素为子序列的起点:此时最长不下降子序列长度为1,后面没有大于等于它的数字,此时最长不下降子序列长度为1,因为只有2号元素本身(15)
以1号元素为子序列的起点:此时最长不下降子序列长度为3,此时包含1、3、4号元素(11,12,13)
3.总结:不管是从前往后推理,还是从后往前推理,都能够求出最长不下降的子序列的长度,其实动态规划就是一个填表的过程,上一个阶段的结果作为求下一个阶段求解的依据。针对这道题目,当我们求出以每个元素为起点或者终点的最长不下降子序列的长度之后,我们还需要找出整个长度行中的最大值,才能找到整个序列的最长不下降子序列长度。
三、代码解题
利用动态规划进行解题,需要找出3个必备条件。
- 确定状态
- 确定边界
- 确定状态转移方程
A.代码1(从前往后推理)
数据结构:
int f[1005]; f[i] 代表以第i号元素为终点最长不下降子序列的长度(确定状态)
int mx = -1; mx用来存放最终最长不下降子序列的长度大小
int data[1005]; data数组用来存放序列数字
输入序列数据和确定边界:
for(int i=1;i<=n;i++) { scanf("%d",&a[i]); f[i]=1; //确定边界 }
其中 ,f[i]数组中的每个元素都需要初始化为1(确定边界),并不是只有f[1]需要初始化为1,其它元素都需要。为什么呢?假设我们只初始化f[1]=1,其它元素不初始化为1,以序列 (11,15,12,13,5,6)为例:
通过观察发现,本来在6号元素位置的长度f[6]应该为2,但是因为没有对f[i]每个元素初始化为1,使得f[6]=1,与我们的期望不符合
核心代码(状态转移方程):
for(int i=2;i<=n;i++) { for(int j=i-1;j>=1;j--) { if(a[i]>=a[j]) f[i]=max(f[i],f[j]+1); } }
找出f[i[中的最大值,求出最长不下降子序列的长度
for(int i=1;i<=n;i++) { mx=max(mx,f[i]); }
完整代码
#include<iostream> #include<cstdio> using namespace std; int n; int a[1001]; int f[1001]; int mx = -1; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); f[i]=1; } for(int i=2;i<=n;i++) { for(int j=i-1;j>=1;j--) { if(a[i]>=a[j]) f[i]=max(f[i],f[j]+1); } } for(int i=1;i<=n;i++) { mx=max(mx,f[i]); } printf("%d",mx); return 0; }
B.代码2(从后往前推理)
数据结构:
int f[1005]; f[i] 代表以第i号元素为起点最长不下降子序列的长度(确定状态)
int mx = -1; mx用来存放最终最长不下降子序列的长度大小
int data[1005]; data数组用来存放序列数字
输入序列数据和确定边界:
for(int i=1;i<=n;i++) { scanf("%d",&a[i]); f[i]=1; //确定边界 }
其中 ,f[i]数组中的每个元素都需要初始化为1(确定边界),并不是只有f[n]需要初始化为1,其它元素都需要。为什么呢?假设我们只初始化f[n]=1,其它元素不初始化为1,以序列 (11,15,12,13,5,6)为例:
通过观察发现,本来在3号元素位置的长度f[3]应该为2,在1号元素位置的长度f[1]应该为3,但是因为没有对f[i]每个元素初始化为1,使得f[3]=1,f[1]=2,与我们的期望不符合
核心代码(状态转移方程):
for(int i=n-1;i>=1;i--) { for(int j=i+1;j<=n;j++) { if(a[i]<=a[j]) { f[i]=max(f[i],f[j]+1); } } }
找出f[i[中的最大值,求出最长不下降子序列的长度
for(int i=1;i<=n;i++) { mx=max(mx,f[i]); }
完整代码
#include<iostream> #include<cstdio> using namespace std; int n; int a[1001]; int f[1001]; //以第i项为起点的最长不下降子序列的长度 int mx = -1; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); f[i]=1; } for(int i=n-1;i>=1;i--) { for(int j=i+1;j<=n;j++) { if(a[i]<=a[j]) { f[i]=max(f[i],f[j]+1); } } } for(int i=1;i<=n;i++) { mx=max(mx,f[i]); } printf("%d",mx); return 0; }
四、在线oj测试
写好代码之后,如何验证你写的是否正确呢?可以登录这个OJ,来测试代码的正确性
http://ybt.ssoier.cn:8088/problem_show.php?pid=1281
需要注意的是,该题求的是最长上升子序列,和最长不下降子序列还是有区别的需要稍微修改一下核心代码,上升子序列要求子序列中的元素不可以相同,而最长不下降子序列中的元素可以相同
可以做如下修改:
//从前往后退 for(int i=2;i<=n;i++) { for(int j=i-1;j>=1;j--) { if(a[i]>a[j]) f[i]=max(f[i],f[j]+1); } } //从后往前推 for(int i=n-1;i>=1;i--) { for(int j=i+1;j<=n;j++) { if(a[i]<a[j]) { f[i]=max(f[i],f[j]+1); } } }
五、提高拓展
以上只是求出的最长不下降子序列的长度,并没有输出最长不下降子序列中的各个元素,可以花点时间去思考一下怎么才能输出最长不下降子序列中的各个元素?。今天的题解就到这里啦 !如果有任何问题欢迎添加博主微信:Q1313135互相讨论学习。我们下期再见~~~
-
最长不下降子序列(LIS)(动态规划)
2022-07-03 14:48:573)为了后续不下降子序列的内容进行输出,也可开一个result数组,result[i] 表示str[i]的前继结点,一个序列的首结点设置为-1,与其他节点进行区分, 其实和第一个程序利用dp的值进行输出内容是一样的。...- 状态设计:dp[i]表示以str[i]结尾的最长不下降子序列长度
- 状态转移方程:dp[i]=max(dp[j]+1,1) (j<i&&str[j]<=str[i]);
- 当然,后面我们还可以输出这个最长不下降子序列的内容,只需要从后面开始枚举dp的值进行递减,只要dp的值与temp(最长子序列长度递减)相等, 就把str[i]的值加到lis中,直到temp==0为止。
- 输出第一个最长不下降子序列的内容呢:不过是从前面开始枚举罢了。
/** 2)状态设计:dp[i]表示以str[i]结尾的最长不下降子序列长度 状态转移方程:dp[i]=max(dp[j]+1,1) (j<i&&str[j]<=str[i]); 当然,后面我们还可以输出这个最长不下降子序列的内容,只需要从后面 开始枚举dp的值进行递减,只要dp的值与temp(最长子序列长度递减)相等, 就把str[i]的值加到lis中,直到temp==0为止。 输出第一个最长不下降子序列的内容呢:不过是从前面开始枚举罢了。 */ /** #include <iostream> #include <string> #include <algorithm> using namespace std; int main() { string str; cout << "input a string:\n"; cin >> str; int len=str.size(); int dp[len],ans=0; //dp[i]表示以str[i]结尾的最长不下降子序列长度 dp[0]=1; //状态转移方程:dp[i]=max(dp[j]+1,1) (j<i&&str[j]<=str[i]) for(int i=1;i<len;++i) { dp[i]=1; for(int j=0;j<i;++j) { if(str[j]<=str[i]&&dp[j]+1>dp[i]) dp[i]=dp[j]+1; } ans=max(ans,dp[i]); } string lis; //lis输出最长不下降子序列 int temp=ans; for(int i=len-1;i>=0;--i) { if(dp[i]==temp) { lis=str[i]+lis; temp从后开始往前寻找结果,当最长不下降序列 --temp; 不止一个结果时,得到的序列是最后一组 } } cout << ans << endl; for(auto a:str) cout << a << ' '; cout << endl; for(auto a:dp) cout << a << ' '; cout << endl; cout << lis << endl; string first; temp=1; for(int i=0;i<len;++i) { if(dp[i]==temp) { first+=str[i]; ++temp; } } cout << "first substr:\n"; cout << first << endl; return 0; } */
3)为了后续不下降子序列的内容进行输出,也可开一个result数组,result[i]
表示str[i]的前继结点,一个序列的首结点设置为-1,与其他节点进行区分,
其实和第一个程序利用dp的值进行输出内容是一样的。/** 3)为了后续不下降子序列的内容进行输出,也可开一个result数组,result[i] 表示str[i]的前继结点,一个序列的首结点设置为-1,与其他节点进行区分, 其实和第一个程序利用dp的值进行输出内容是一样的 */ #include <iostream> #include <string> #include <algorithm> using namespace std; int main() { string str; cout << "input a string:\n"; cin >> str; int len=str.size(); int dp[len]; //dp[i]表示以str[i]结尾的最长不下降子序列长度 dp[0]=1; //状态转移方程:dp[i]=max(dp[j]+1,1) (j<i&&str[j]<=str[i]) int result[len]; //result[i]表示str[i]的前继结点 result[0]=-1; //一个序列的首结点设置为-1,与其他节点进行区分 for(int i=1;i<len;++i) { dp[i]=1; result[i]=-1; for(int j=0;j<i;++j) { if(str[j]<=str[i]&&dp[j]+1>dp[i]) { dp[i]=dp[j]+1; result[i]=j; } } } int p=0,imax=0; for(int i=0;i<len;++i) { if(dp[i]>imax) { imax=dp[i]; p=i; } } string lis; for(;p!=-1;) { lis=str[p]+lis; p=result[p]; } cout << imax << endl; cout << lis << endl; cout << "调试:\n"; for(auto a:str) cout << a << ' '; cout << endl; for(auto a:dp) cout << a << ' '; cout << endl; for(auto a:result) cout << a << ' '; cout << endl; return 0; }
-
【动态规划】求最长不下降序列
2018-09-22 15:55:52求最长不下降序列 Description 设有n(n&lt;=1000)个不相同的整数(小于32767)组成的数列,记为: a1,a2,…,an,其中任意两个数不相同。 例如:3,18,7,14,10,12,23,41,16,24。 若有 且有 。则称为长度为e...求 最 长 不 下 降 序 列 求最长不下降序列 求最长不下降序列
Description
设有n(n<=1000)个不相同的整数(小于32767)组成的数列,记为:
a1,a2,…,an,其中任意两个数不相同。
例如:3,18,7,14,10,12,23,41,16,24。
若有 且有 。则称为长度为e的不下降序列。如上例中,3,18,23,24为一个长度为4的不下降序列,同时也有3,7,10,12,16,24长度为6的不下降序列。程序要求,当原始数列给出后,求出最长的不下降数列的长度。
Sample Input
10
3 18 7 14 10 12 23 41 16 24
Sample Output
6
解题思路
用两个循环来枚举到哪个个数的最长不下降序列和这个数可能连接到的不下降序列。
#include<cstdio> #include<iostream> using namespace std; int num,n,a[1001],sum[1001]; int main() { scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d",&a[i]); sum[i]=1; for (int j=1;j<i;j++) if (a[j]<a[i]&&sum[j]>=sum[i])//如果a[j]比a[i]小并且第j个数的不下降序列比当前的长或相等 sum[i]=sum[j]+1; num=max(num,sum[i]);//判断当前段是否为最优 } printf("%d",num); }
-
最长不下降子序列nlogn算法详解
2020-12-19 12:27:08解决的问题:给定一个序列,求最长不下降子序列的长度(nlogn的算法没法求出具体的序列是什么)定义:a[1..n]为原始序列,d[k]表示长度为k的不下降子序列末尾元素的最小值,len表示当前已知的最长子序列的长度。... -
最长不降子序列算法详解
2018-08-18 13:06:27最长不降子序列(LIS)算法 自己乱搞了个数据 输入 10 1 3 7 3 6 1 3 2 4 5 输出 6 显然上述数据中最长不降子数列为{1,3,3,3,4,5},长度为六。 一、暴力dp 很容易就能想到的方法: 对于一个序列A[1..n],f... -
最长不下降子序列(C++动态规划)
2022-02-01 09:26:08#include<bits/stdc++.h> using namespace std;... //当只有一个字符的时候 最长上升子序列为1 for(int i=1;i<=n;i++) dp[i] = 1; for(int i=1;i<=n;i++) cin>>a[i]; for(int i. -
【算法】动态规划 - 最长不下降子序列(LIS)
2020-02-14 15:04:26最长不下降子序列(Longest Increasing Sequence):在一个数字序列中,找到一个最长的子序列(可以不连续),使得这样的子序列是不下降(即非递减)的。 例如序列 a = {1, 2, 3, -1, -2, 7, 9},它的最长不下降子... -
429-动态规划算法-最长非降子序列LIS
2021-08-17 10:55:55显然,5和3不能构成非降子序列。3和4就可以构成非降子序列。以此类推。 最长的非降子序列是3479 朴素解法:不一定得到最优解,无效的解法 但是要求算法时间复杂度:O(n^2) 动态规划算法解决 #include <iostream&... -
算法设计与分析:动态规划算法思想的应用 --最长非降子序列(非连续)问题
2022-05-20 22:51:54算法设计与分析:动态规划算法思想的应用 --最长非降子序列(非连续)问题 -
动态规划之最长不下降子序列(LIS)
2022-01-24 09:34:16最长不下降子序列(LIS)——动态规划求解 -
动态规划-最长不下降子序列(LIS)
2020-03-22 20:22:24最长不下降子序列(Longest Increasing Subsequence)是动态规划中的一个非常经典的问题: 在一个数字序列中,找到一个最长的子序列(可以不连续),使得这个子序列是不下降(非递减)的 例如 A = {1, 2, 3, -1, -... -
算法设计经典练习——动态规划解最长不下降子序列
2020-04-07 23:46:57求最长不下降子序列 简单动态规划问题 ... -
[动态规划]最长不降子序列-NlogN算法
2015-06-19 16:49:06NlogN算法精髓在于设立数组 -
算法基础:使用动态规划法解决最长上升子序列问题
2020-11-01 18:59:43这篇文章继续介绍使用动态规划法解决LIS问题的方法。 -
Contest100000627 - 《算法笔记》11.3小节——动态规划专题->最长不下降子序列(LIS)
2019-02-23 17:05:45最长不下降子序列(Longest Increasing Sequence,LIS):在一个数字序列中,找到一个最长的子序列(可以不连续),使得这个子序列是不下降的(非递减)的。这也是动态规划的经典题目。 穷举法的时间复杂度为 ,... -
算法导论随笔(十三):动态规划与最长公共子序列(LCS)
2020-11-09 06:14:36动态规划(Dynamic programming)与前文算法导论随笔(二): 归并排序与分治策略中提到的分治策略类似,都是通过组合子问题的解来求解原问题。 与分治策略不同的是,在分治策略中,每一个子问题是独立的,而动态规划中每... -
【算法】【动态规划】最长上升子序列和最长不下降子序列
2021-10-25 10:27:20参考视频:9.67 最长不下降子序列——信息学竞赛培训课程_哔哩哔哩_bilibili 给出一个无序的数组 例如:5 8 8 6 2 6 7 则最长上升子序列为5 6 7 最长不下降子序列为5 6 6 7 核心思想:遍历数组,以被遍历的数为... -
动态规划 最长不下降序列
2020-04-18 15:43:42最长不下降序列题目:解析:代码: 题目: 一个正整数序列b1,b2,…,bn,若下标为i1<i2<…<ik且有bi1<=bi2<=…<=bik,则称存在一个长度为k的不下降序列。可能有多个不下降序列,输出最长序列的... -
动态规划2:最长不下降子序列--连续序列+不连续序列
2020-02-27 00:46:12//最长不下降子序列--连续+不连续 #include <cstdio> #include "vector" #include "algorithm" using namespace std; const int maxn = 10010; int A[maxn], dp[maxn];//A存放数字序列 dp存放以A[i]结尾... -
最长非降子序列(动态规划dp dynamic programming)
2021-11-11 11:25:43所以,最长非降子序列,不难理解就是从这些子序列中挑出一个最长的子序列。 求解最长非降子序列长度思路: 总体思路就是倒着看,去看分别以每一个元素开头的最长非降子序列的长度,如果前面的数小于后面的某一个数,... -
[动态规划]最长不降子序列问题-N*N算法
2015-06-19 16:35:17最长不降子序列N*N算法 状态转移方程:dp[i]=max(dp[j]+1)(其中j=0~i-1) 即i之前最长的加上1便是到i位置最长的序列。 算法复杂度N*N 代码:此例是严格递增的最长序列 #include #include int main() { int i,j;... -
最长公共子序列(LCS)动态规划的算法优化
2018-10-16 23:04:03最长公共子序列求解问题是一种典型的动态规划问题。此文章以http://nyoj.top/problem/1409 或http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=36为例说明最长子序列的动态规划算法如何优化。 关于最长公共... -
动态规划算法3——最长上升子序列
2019-04-18 11:39:00类似的,我们可以通过二分查找中改变“上确界”和“下确界”,以及符号(“<”和“”或“>”、“>=”等),求出最长不下降、不上升、严格下降子序列等问题。 转载于:... -
动态规划之最长递增子序列
2021-04-06 23:04:22最长递增子序列的问题就是: 给定序列A=a0,a1,a2,…,an, 如果它的子序列b1,b2,…,bn满足b1<b2<b3<…<bn 则称这个子序列是一个递增子序列。A的所有子序列中,最长的那个就是最长递增子序列(LIS) ... -
最长不下降子序列的O(nlogn)算法
2018-01-18 11:00:54用O(NlogN)的复杂度求 最长不下降子序列。深度挖掘数据下的规律,可以加速dp的推导。 -
动态规划入门---最长公共子序列
2021-02-15 21:58:12动态规划动态规划(DP,Dynamic Programming)定义动态规划问题的特点最长公共子序列问题(LCS)。分析实现特点动态规划的精髓总结作业 动态规划(DP,Dynamic Programming) 我认为动态规划是所有算法中最最重要... -
动态规划算法下的序列问题:最长公共子序列问题和最大子段和问题
2020-04-20 09:54:11本篇主要介绍最长公共子序列问题和最大子段和问题 1、最长公共子序列问题 什么是最长公共子序列 给定一个序列X=<x1,x2,x3,x4…,xm>,另一个序列Z=<z1,z2,z3,z4…,zk>,若存在一个严格递增的X的下标序列&... -
P1439 【模板】最长公共子序列 (最长不下降序列 (单调队列优化))
2021-08-20 21:41:52洛谷最长公共子序列(其实是最长不下降子序列的模板题) 解题思路: 只要有一点DP基础,就知道这题肯定是用最长公共子序列的DP来做。 但是我们再看看这数据范围 对于 100% 的数据 n<=105n<=10^5n<=105。...