精华内容
下载资源
问答
  • 最长不降子序列(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.

    谢谢!


    欢迎指正错误^_^

    展开全文
  • 最长不下降序列题目:解析:代码: 题目: 一个正整数序列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;
    }
    
    展开全文
  • 最长不下降子序列 简单动态规划问题 ...

    求最长不下降子序列 简单动态规划问题

    题目
    求最长不下降子序列

    描述
    设有由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的不下降序列。程序要求,当原数列出之后,求出最长的不下降序列。

      
    
    例如13791638243718441921226315。
    例中13161819212263就是一个长度为7的不下降序列,
    同时也有79161819212263组成的长度为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&lt;&lt;Max_f&lt;&lt;endl;
    	if(ans[Max_f]==-1){
    		return;
    	} //终止条件 
    	else {
    		findans(ans[Max_f]);
    		cout&lt;&lt;a[ans[Max_f]]&lt;&lt;" ";
    	} //输出 
    	return ;
    }
    int main(){
    	memset(ans,-1,sizeof(ans)); //数组归零 
    	
    	cin&gt;&gt;n; //输入 
    	for(int i=0;i&lt;n;i++){
    		cin&gt;&gt;a[i]; dp[i]=1;
    	} 
    	
    	for(int i=1;i&lt;n;i++){
    		for(int j=0;j&lt;i;j++) 
    			if(a[j]&lt;=a[i]){
    					if(dp[j]+1&gt;dp[i])
    					ans[i]=j; //记录前一个位置
    					dp[i]=max(dp[j]+1,dp[i]); //状态转移方程 
    			}
    	}
    	
    	for(int i=0;i&lt;n;i++){
    		 if(dp[i]&gt;Max){
    		 	Max=dp[i];
    		 	Max_f=i;
    		 } 
    	} //找出Max和Max的位置 
    	
    	cout&lt;&lt;"max="&lt;&lt;Max&lt;&lt;endl; //输出 
    	findans(Max_f); //递归输出 
    	cout&lt;&lt;a[Max_f]&lt;&lt;endl; //防止末尾空格 
    	
    	return 0;
    	}
    

    代码仅供参考,让我们共同学习!

    展开全文
  • 最长不降子序列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算法精髓在于设立数组
  • 最长不下降子序列(Longest Increasing Sequence):在一个数字序列中,找到一个最长子序列(可以连续),使得这样的子序列不下降(即非递减)的。 例如序列 a = {1, 2, 3, -1, -2, 7, 9},它的最长不下降子...
  • 显然,5和3能构成非降子序列。3和4就可以构成非降子序列。以此类推。 最长的非降子序列是3479 朴素解法:一定得到最优解,无效的解法 但是要求算法时间复杂度:O(n^2) 动态规划算法解决 #include <iostream&...
  • 【前言】动态规划:与分治法相似,即通过组合问题来求解原问题,不同的是分治法是将问题划分为互不相交的问题,递归求解问题,再将他们组合起来求出原问题的解。 动态规划则应用于问题重叠的情况,通常用来...
  • 一、概念明确 先来看一串数字:(20,17,19,22,4,7,10,12,5,2,13) 1.序列:像以上排成一列的数字,我们叫它序列,其中每个数字,可以被称为一个元素。...3.不下降子序列不下降的意思是上升或者相...
  • 题目描述 ...求序列b1,b2,b3,……,bm中最大不下降序列的长度。 输入格式 第一行为n,第二行为用空格隔开的n个整数。 输出格式 第一行为输出最大个数max。 输入输出样例 输入 #1 14 13 7 9 16 38 24 37 18 44
  • 动态规划——最长降子序列

    千次阅读 2016-04-20 13:22:57
    动态规划算法求解最长降子序列问题
  • 一个序列有N个数:A[1],A[2],…,A[N],求出最长降子序列的长度 思路分析 这是博客http://hawstein.com/posts/dp-novice-to-advanced.html 上的第二个例子 编写代码 递归的代码看起啦更加好理解一些,不过...
  • O(nlogn)的算法关键是它建立了一个数组temp[],temp[i]表示长度为i的不下降序列中结尾元素的最小值,用top表示数组目前的长度,算法完成后top的值即为最长不下降子序列的长度。 设当前的以求出的长度为top,则判断...
  • 动态规划最长上升子序列两种算法 一、O(N2){O(N^2)}O(N2)算法 #include&lt;bits/stdc++.h&gt; using namespace std; int main(){ int n; while(cin &gt;&gt; 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 请在序列中...
  • 最长不下降子序列(Longest Increasing Subsequence)是动态规划中的一个非常经典的问题: 在一个数字序列中,找到一个最长子序列(可以连续),使得这个子序列不下降(非递减)的 例如 A = {1, 2, 3, -1, -...
  • 最长上升子序列  ...
  • 最长不降子序列是这样一个问题:    下面介绍动态规划的做法。  令 dp[i]表示以 A[i]结尾的最长不下降序列长度。这样对 A[i]来说就会有两种可能: 如果存在 A[i]之前的元素 A[j] (j<i),使得 A[j]...
  • 这篇文章继续介绍使用动态规划法解决LIS问题的方法。
  • 之前我在博客里写,PAT甲级的例题似乎没有...另一方面,之前接触过最大子序列和、最长公共子序列最长回文子序列,但今天第一次接触最长不下降上升/下降/上升)子序列。 这一题我最开始是使用深度优先搜索求解...
  • 分析来手写一下求取最长降子序列的过程,用d[i]表示第i个数所对应的最长降子序列的长度d[0] = 0; d[1] = 1;//5是第一个数,所以只有5这一个数,d[1]=1 d[2] = 1;//因为3之前的所有数都大于3,所以只有3这一个数 d...
  • 最长公共子序列求解问题是一种典型的动态规划问题。此文章以http://nyoj.top/problem/1409 或http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=36为例说明最长子序列的动态规划算法如何优化。 关于最长公共...
  • 最长不下降子序列(线性动态规划)    我们知道,递推就是按照递推公式不断往前求解的一个过程,对于当前,只有一个状态描述当前的值。若某些问题并非由一个状态而是由多个状态不断推导,那么这种方法就是动态规划...
  • 动态规划算法解LCS问题 作者 July 二零一零年十二月三十一日 本文参考:微软面试100题系列V0.1版第19、56题、算法导论、维基百科。 第一部分、什么是动态规划算法 ok,咱们先来了解下什么...
  • 最长递增子序列的问题就是: 给定序列A=a0,a1,a2,…,an, 如果它的子序列b1,b2,…,bn满足b1<b2<b3<…<bn 则称这个子序列是一个递增子序列。A的所有子序列中,最长的那个就是最长递增子序列(LIS) ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,601
精华内容 4,640
关键字:

动态规划最长不下降序列算法