题目
求最长不下降子序列
描述
设有由n(1≤n≤200)个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)b(1)、b(2)、……、b(n)且b(i)≠b(j)(i≠j)b(i)≠b(j)(i≠j)，若存在i<i2<i3<…<iei1<i2<i3<…<ie且有b(i1)<b(i2)<…<b(ie)b(i1)<b(i2)<…<b(ie)则称为长度为e的不下降序列。程序要求，当原数列出之后，求出最长的不下降序列。
-
最长不降子序列算法详解
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...展开全文最长不降子序列（LIS）算法
自己乱搞了个数据
输入 10 1 3 7 3 6 1 3 2 4 5 输出 6显然上述数据中最长不降子数列为{1,3,3,3,4,5}，长度为六。
一、暴力dp
很容易就能想到的方法：
对于一个序列A[1..n]，f[i]表示从Ai到An的最长不降子序列，
则转移方程为：f[i]:=max(f[i],f[j+1])【i:=n downto 1;j:=i+1 to n;f[i]初始为1】
时间复杂度为 O(n^2)
代码：var n,i,j,max:longint; a,f:array[1..10000]of longint; function max1(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; begin readln(n); for i:=1 to n do read(a[i]); for i:=n downto 1 do begin f[i]:=1; for j:=i+1 to n do if a[j]>=a[i] then f[i]:=max1(f[j]+1,f[i]); end; for i:=1 to n do if f[i]>max then max:=f[i]; writeln(max); end.显然，在数据>10000时会T。
二、单调队列二分优化
令一个数组B[1..lenb]
b[i]表示从1到i中最长不降子序列中最后一个元素
可以发现B是单调不降的
我们每读入一个Ai，只需维护B单调不降即可
维护用二分查找，查找b[i]满足b[i-1 <= x < b[i+1]，复杂度 O(log n)
最后输出lenb即可
总复杂度O(n log n)
代码：var n,i,x,l,r,w,mid:longint; a:array[0..1000000]of longint; begin readln(n); for i:=1 to n do begin read(x); if x>=a[w] then begin inc(w);a[w]:=x; end else begin l:=1;r:=w; while l<r do begin mid:=(l+r) div 2; if a[mid]<=x then l:=mid+1 else r:=mid; end; a[r]:=x; end; end; writeln(w); end.谢谢！
欢迎指正错误^_^
-
动态规划 最长不下降序列
2020-04-18 15:43:42最长不下降序列题目：解析：代码： 题目： 一个正整数序列b1，b2，…，bn，若下标为i1<i2<…<ik且有bi1<=bi2<=…<=bik，则称存在一个长度为k的不下降序列。可能有多个不下降序列，输出最长序列的...展开全文题目：
一个正整数序列b1，b2，…，bn，若下标为i1<i2<…<ik且有bi1<=bi2<=…<=bik，则称存在一个长度为k的不下降序列。可能有多个不下降序列，输出最长序列的长度。
解析：
这道题
也是动态规划的题目
和以前
发布的那道
万达广场
有一些相似
这道题的精髓
就在于
从第2个到第n个
都要选择前面符合条件的数字中最大的一个
再+1
这道题
非常简单
没啥么好说的
下面是代码
代码：
#include<bits/stdc++.h> #include<iostream> #include<cstdlib> #include<cstdio> using namespace std; int n,a[1001],b[1001],maxx=0; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; b[i]=1; } for(int i=2;i<=n;i++) { maxx=0; for(int j=1;j<=i-1;j++) { if(a[j]<=a[i]&&b[j]>maxx) maxx=b[j]; } b[i]=maxx+1; } maxx=0; for(int i=1;i<=n;i++) { if(b[i]>maxx) maxx=b[i]; } cout<<maxx<<endl; return 0; }
-
算法设计经典练习——动态规划解最长不下降子序列
2020-04-07 23:46:57求最长不下降子序列 简单动态规划问题 ...展开全文例如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题目思路
简单的动态规划，简单推出状态转移方程，再利用dp数组即可。#include <iostream> #include <string.h> using namespace std; int ans[200];int Max=0,Max_f;int n,a[1000]={},dp[1000]={},tot=0; void findans(int Max_f){ //cout<<Max_f<<endl; if(ans[Max_f]==-1){ return; } //终止条件 else { findans(ans[Max_f]); cout<<a[ans[Max_f]]<<" "; } //输出 return ; } int main(){ memset(ans,-1,sizeof(ans)); //数组归零 cin>>n; //输入 for(int i=0;i<n;i++){ cin>>a[i]; dp[i]=1; } for(int i=1;i<n;i++){ for(int j=0;j<i;j++) if(a[j]<=a[i]){ if(dp[j]+1>dp[i]) ans[i]=j; //记录前一个位置 dp[i]=max(dp[j]+1,dp[i]); //状态转移方程 } } for(int i=0;i<n;i++){ if(dp[i]>Max){ Max=dp[i]; Max_f=i; } } //找出Max和Max的位置 cout<<"max="<<Max<<endl; //输出 findans(Max_f); //递归输出 cout<<a[Max_f]<<endl; //防止末尾空格 return 0; }代码仅供参考，让我们共同学习！
-
[动态规划]最长不降子序列问题-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;...展开全文最长不降子序列N*N算法
状态转移方程：dp[i]=max(dp[j]+1)(其中j=0~i-1) 即i之前最长的加上1便是到i位置最长的序列。
算法复杂度N*N
代码：此例是严格递增的最长序列
#include<stdio.h> #include<string.h> int main() { int i,j; int n,max; int a[1001],list[1001]; while(scanf("%d",&n)!=EOF) { memset(a,0,sizeof(a)); for(i=0;i<n;i++) scanf("%d",&a[i]); max=0; for(i=0;i<n;i++) { list[i]=1; for(j=0;j<i;j++) if(a[i]>a[j] && list[i]<list[j]+1) list[i]=list[j]+1; if(max<list[i]) max=list[i]; } printf("%d\n",max); } return 0; }
-
[动态规划]最长不降子序列-NlogN算法
2015-06-19 16:49:06NlogN算法精髓在于设立数组 -
【算法】动态规划 - 最长不下降子序列（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&... -
动态规划之最长递增子序列 最长不重复子串 最长公共子序列
2016-05-11 16:19:40【前言】动态规划：与分治法相似，即通过组合子问题来求解原问题，不同的是分治法是将问题划分为互不相交的子问题，递归求解子问题，再将他们组合起来求出原问题的解。 动态规划则应用于子问题重叠的情况，通常用来... -
动态规划之最长不下降子序列
2021-08-11 12:30:26一、概念明确 先来看一串数字：(20,17,19,22,4,7,10,12,5,2,13) 1.序列：像以上排成一列的数字，我们叫它序列，其中每个数字，可以被称为一个元素。...3.不下降子序列：不下降的意思是上升或者相... -
动态规划--最长不下降子序列
2021-08-07 14:25:26题目描述 ...求序列b1,b2,b3,……,bm中最大不下降序列的长度。 输入格式 第一行为n,第二行为用空格隔开的n个整数。 输出格式 第一行为输出最大个数max。 输入输出样例 输入 #1 14 13 7 9 16 38 24 37 18 44 -
动态规划——最长非降子序列
2016-04-20 13:22:57动态规划算法求解最长非降子序列问题 -
《最长非降子序列》 动态规划算法入门
2014-05-25 17:36:36一个序列有N个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度 思路分析 这是博客http://hawstein.com/posts/dp-novice-to-advanced.html 上的第二个例子 编写代码 递归的代码看起啦更加好理解一些，不过... -
最长不下降序列nlogn算法
2013-05-05 19:55:58O(nlogn)的算法关键是它建立了一个数组temp[]，temp[i]表示长度为i的不下降序列中结尾元素的最小值，用top表示数组目前的长度，算法完成后top的值即为最长不下降子序列的长度。 设当前的以求出的长度为top，则判断... -
动态规划求最长上升子序列两种算法
2018-11-06 14:37:49动态规划求最长上升子序列两种算法 一、O(N2){O(N^2)}O(N2)算法 #include<bits/stdc++.h> using namespace std; int main(){ int n; while(cin >> n){ int v[n+1]; for(int i = 1;... -
最长非降子序列 动态规划 java
2017-02-17 16:18:40给定一个由n个正整数组成的序列，从该序列中删除若干个整数，使剩下的整数组成非降子序列，求最长的非降子序列。 例如，由12个正整数组成的序列为： 48，16，45，47，52，46，36，28，46，69，14，42 请在序列中... -
动态规划-最长不下降子序列（LIS）
2020-03-22 20:22:24最长不下降子序列（Longest Increasing Subsequence）是动态规划中的一个非常经典的问题： 在一个数字序列中，找到一个最长的子序列（可以不连续），使得这个子序列是不下降（非递减）的 例如 A = {1, 2, 3, -1, -... -
动态规划——最长上升子序列问题 两种角度及优化算法
2018-08-12 18:48:22最长上升子序列 ... -
动态规划——最长不下降子序列（LIS）
2018-02-09 10:27:00最长不降子序列是这样一个问题： 下面介绍动态规划的做法。 令 dp[i]表示以 A[i]结尾的最长不下降序列长度。这样对 A[i]来说就会有两种可能： 如果存在 A[i]之前的元素 A[j] (j<i)，使得 A[j]... -
算法基础：使用动态规划法解决最长上升子序列问题
2020-11-01 18:59:43这篇文章继续介绍使用动态规划法解决LIS问题的方法。 -
浙大 PAT 甲级 1045 Favorite Color Stripe 经典动态规划：最长不下降子序列
2019-08-18 20:18:40之前我在博客里写，PAT甲级的例题似乎没有...另一方面，之前接触过最大子序列和、最长公共子序列、最长回文子序列，但今天第一次接触最长不下降（不上升/下降/上升）子序列。 这一题我最开始是使用深度优先搜索求解... -
动态规划-最长非降子序列
2016-08-09 21:46:07分析来手写一下求取最长非降子序列的过程，用d[i]表示第i个数所对应的最长非降子序列的长度d[0] = 0; d[1] = 1;//5是第一个数，所以只有5这一个数,d[1]=1 d[2] = 1;//因为3之前的所有数都大于3，所以只有3这一个数 d... -
最长公共子序列（LCS）动态规划的算法优化
2018-10-16 23:04:03最长公共子序列求解问题是一种典型的动态规划问题。此文章以http://nyoj.top/problem/1409 或http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=36为例说明最长子序列的动态规划算法如何优化。 关于最长公共... -
【线性动态规划】最长不下降子序列（LIS）
2021-01-25 15:31:03最长不下降子序列（线性动态规划） 我们知道，递推就是按照递推公式不断往前求解的一个过程，对于当前，只有一个状态描述当前的值。若某些问题并非由一个状态而是由多个状态不断推导，那么这种方法就是动态规划... -
动态规划算法解最长公共子序列LCS问题
2014-12-18 23:28:56动态规划算法解LCS问题 作者 July 二零一零年十二月三十一日 本文参考：微软面试100题系列V0.1版第19、56题、算法导论、维基百科。 第一部分、什么是动态规划算法 ok，咱们先来了解下什么... -
动态规划之最长递增子序列
2021-04-06 23:04:22最长递增子序列的问题就是： 给定序列A=a0,a1,a2,…,an， 如果它的子序列b1,b2,…,bn满足b1<b2<b3<…<bn 则称这个子序列是一个递增子序列。A的所有子序列中，最长的那个就是最长递增子序列（LIS） ...
收藏数
11,601
精华内容
4,640