精华内容
下载资源
问答
  • 2021-01-15 01:54:33

    今天花了很长时间终于弄懂了这个算法……毕竟找一个好的讲解真的太难了,所以励志我要自己写一个好的讲解QAQ

    这篇文章是在懂了这个问题n^2解决方案的基础上学习。

    解决的问题:给定一个序列,求最长不下降子序列的长度(nlogn的算法没法求出具体的序列是什么)

    定义:a[1..n]为原始序列,d[k]表示长度为k的不下降子序列末尾元素的最小值,len表示当前已知的最长子序列的长度。

    初始化:d[1]=a[1]; len=1; (0个元素的时候特判一下)

    现在我们已知最长的不下降子序列长度为1,末尾元素的最小值为a[1],那么我们让i从2到n循环,依次求出前i个元素的最长不下降子序列的长度,循环的时候我们只需要维护好d这个数组还有len就可以了。

    关键问题就是怎么维护?

    可以看出我们是要用logn的复杂度维护的。实际上利用了d数组的一个性质:单调性。(长度更长了,d[k]的值是不会减小的)

    考虑新进来一个元素a[i]:

    如果这个元素大于等于d[len],直接让d[len+1]=a[i],然后len++。这个很好理解,当前最长的长度变成了len+1,而且d数组也添加了一个元素。

    如果这个元素小于d[len]呢?说明它不能接在最后一个后面了。那我们就看一下它该接在谁后面。

    准确的说,并不是接在谁后面。而是替换掉谁。因为它接在前面的谁后面都是没有意义的,再接也超不过最长的len,所以是替换掉别人。那么替换掉谁呢?就是替换掉那个最该被它替换的那个。也就是在d数组中第一个大于它的。第一个意味着前面的都小于等于它。假设第一个大于它的是d[j],说明d[1..j-1]都小于等于它,那么它完全可以接上d[j-1]然后生成一个长度为j的不下降子序列,而且这个子序列比当前的d[j]这个子序列更有潜力(因为这个数比d[j]小)。所以就替换掉它就行了,也就是d[j]=a[i]。其实这个位置也是它唯一能够替换的位置(前面的替了不满足d[k]最小值的定义,后面替换了不满足不下降序列)

    至于第一个大于它的怎么找……STL upper_bound。每次复杂度logn。

    至此,我们就神奇的解决了这个问题。按照这个思路,如果需要求严格递增的子序列怎么办?

    仍然考虑新进来一个元素a[i]:

    如果这个元素大于d[len],直接让d[len+1]=a[i],然后len++。这个很好理解,当前最长的长度变成了len+1,而且d数组也添加了一个元素。

    如果这个元素小于等于d[len]呢?说明它不能接在最后一个后面了。那我们就看一下它该接在谁后面。

    同样的道理,只是upper_bound的时候要特判一下。每次复杂度logn。

    下面是最长不下降子序列的代码

    //最长不下降子序列nlogn Song

    #include#include

    using namespacestd;

    int a[40005];

    int d[40005];

    intmain()

    {

    intn;

    scanf("%d",&n);

    for (int i=1;i<=n;i++) scanf("%d",&a[i]);

    if (n==0) //0个元素特判一下

    {

    printf("0\n");

    return 0;

    }

    d[1]=a[1]; //初始化

    int len=1;

    for (int i=2;i<=n;i++)

    {

    if (a[i]>=d[len]) d[++len]=a[i]; //如果可以接在len后面就接上

    else //否则就找一个最该替换的替换掉

    {

    int j=upper_bound(d+1,d+len+1,a[i])-d; //找到第一个大于它的d的下标

    d[j]=a[i];

    }

    }

    printf("%d\n",len);

    return 0;

    }

    想了一晚上这个问题终于想通了。前面说的“最该替换的位置”实际上不是很精确,那个位置替换掉是它唯一能够替换的位置,之所以要替换,就是为了维护d这个数组,让它始终满足最初的定义。

    更多相关内容
  • 动态规划之最长不下降子序列

    千次阅读 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个必备条件。

    1. 确定状态
    2. 确定边界
    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互相讨论学习。我们下期再见~~~

     

    展开全文
  • 最长不下降子序列

    2020-08-12 20:07:45
    最长不下降子序列 Description 一个数的序列bi,当b1 <= b2 <= … < =bS的时候,我们称这个序列是下降的。对于给定的一个序列(a1, a2, …, aN),我们可以得到一些下降的子序列(ai1, ai2, …, aiK),...

    最长不下降子序列
    Description
    一个数的序列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)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8)。

    Input
    多组cas , 每组cas 两行:

    第一行 输入一个数 n (n < 10000), 表示有n个数

    第二行 n个数, 分别代表每个数;

    Output
    每个cas 一行 输出 该书数列的最长的长度 ;

    Sample Input
    7
    1 7 3 5 9 4 8
    Sample Output
    4

    #include<bits/stdc++.h>
    using namespace std;
    int a[10001],n,dp[10001];
    int main()
    {
    	int i,mx,j;
    	while(cin>>n)
    	{
    		for(i=1;i<=n;i++)
    		{
    			scanf("%d",&a[i]);
    		}
    		mx=0;
    		for(i=n;i>=1;i--)
    		{
    			dp[i]=1;
    			for(j=i+1;j<=n;j++)
    			{
    				if(a[i]<=a[j])
    				{
    					dp[i]=max(1+dp[j],dp[i]);
    				}
    			}
    			mx=max(dp[i],mx);
    		}
    		printf("%d\n",mx);
    	}
    	return 0;
    }
    

    最长不下降子序列(Onlogn算法)
    Description
    一个数的序列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)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8)。

    Input
    多组cas , 每组cas 两行:

    第一行 输入一个数 n (n < 10000), 表示有n个数

    第二行 n个数, 分别代表每个数;

    Output
    每个cas 一行 输出 该书数列的最长的长度 ;

    Sample Input
    7
    1 7 3 5 9 4 8
    Sample Output
    4
    lower_boumd

    #include<bits/stdc++.h>
    using namespace std;
    int a[10001],b[10001];
    int main()
    {
    	int n,i,c,wc;
    	while(cin>>n)
    	{
    		for(i=1;i<=n;i++)
    		{
    			scanf("%d",&a[i]);
    		}
    		c=1;
    		b[n-c+1]=a[n];
    		for(i=n-1;i>=1;i--)
    		{
    			if(a[i]<=b[n-c+1])
    			{
    				c++;
    				b[n-c+1]=a[i];
    			}
    			else
    			{
    				if(a[i]>b[n])
    				{
    					b[n]=a[i];
    				}
    				else
    				{
    					wc=lower_bound(b+n-c+1,b+n,a[i])-b-1;
    					b[wc]=a[i];
    				}
    			}
    		}
    		printf("%d\n",c);
    	}
        return 0;
    } 
    

    普通二分

    #include<bits/stdc++.h>
    using namespace std;
    #define MAXN 10001
    int a[MAXN],b[MAXN],ans,n;
    void shur();
    int get();
    void shuc();
    int erfen(int x,int l,int r);
    int main()
    {
    	while(cin>>n)
    	{
    		shur();
    		ans=get();
    		shuc();
    	}
    	return 0;
    }
    void shur()
    {
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%d",&a[i]);
    	}
    }
    int get()
    {
    	int c,wc;
    	c=1;
    	b[1]=a[n];
    	for(int i=n-1;i>=1;i--)
    	{
    		if(a[i]<=b[c])
    		{
    			c++;
    			b[c]=a[i];
    		}
    		else if(a[i]>b[1])
    		{
    			b[1]=a[i];
    		}
    		else
    		{
    			wc=erfen(a[i],c,1);
    			b[wc]=a[i];
    		}
    	}
    	return c;
    }
    void shuc()
    {
    	printf("%d\n",ans);
    }
    int erfen(int x,int l,int r)
    {
    	int zj,y;
    	if(l==r)
    	{
    		y=l;
    		return y;
    	}
    	zj=(l+r)/2;
    	if(x>b[zj])
    	{
    		y=erfen(x,zj,r);
    	}
    	else
    	{
    		y=erfen(x,l,zj+1);
    	}
    	return y;
    }
    

    Description

    Input
    本问题有多组测试数据,对于每组测试数据,输入有两行;第一行n表示序列的元素个数,1<=n<=10000;第二行是用空格隔开的n个整数,表示由n个整数组成的序列。

    Output
    对于每一组测试数据,输出有两行,第一行为最长的子序列的长度;第二行是用空格隔开的子序列,行尾没有空格。

    Sample Input
    7
    1 7 3 5 9 4 8
    14
    13 7 9 16 38 24 37 18 44 19 21 22 63 15
    Sample Output
    4
    1 3 5 9
    8
    7 9 16 18 19 21 22 63

    #include<bits/stdc++.h>
    using namespace std;
    int a[10001],n,dp[10001],b[10001],h;
    int main()
    {
    	int i,mx,j;
    	while(cin>>n)
    	{
    		for(i=1;i<=n;i++)
    		{
    			scanf("%d",&a[i]);
    		}
    		mx=0;
    		h=1;
    		for(i=n;i>=1;i--)
    		{
    			dp[i]=1;
    			b[i]=i;
    			for(j=i+1;j<=n;j++)
    			{
    				if(a[i]<=a[j]&&dp[i]<dp[j]+1)
    				{
    					dp[i]=dp[j]+1;
    					b[i]=j;
    				}
    			}
    			if(mx<=dp[i])
    			{
    				h=i;
    				mx=dp[i];
    			}
    		}
    		printf("%d\n",mx);
    		printf("%d",a[h]);
    		h=b[h]; 
    		for(i=1;i<mx;i++)
    		{
    			printf(" %d",a[h]);
    			h=b[h];
    		}
    		printf("\n");
    	}
    	return 0;
    }
    
    展开全文
  • 唔,最长不下降子序列最长上升子序列曾是困扰蒟蒻多时的一个问题,应该也有一些人分清这2个的求法吧。首先n^2算法肯定是都能分清的,因为下降和上升的区别是连续的2个能能相等,只需要在判断的时候判一下...

    唔,最长不下降子序列与最长上升子序列曾是困扰蒟蒻多时的一个问题,应该也有一些人分不清这2个的求法吧。

    首先n^2算法肯定是都能分清的,因为不下降和上升的区别是连续的2个能不能相等,只需要在判断的时候判一下是不是相等就可以了。

    最长不下降子序列代码:

    8f900a89c6347c561fdf2122f13be562.png

    961ddebeb323a10fe0623af514929fc1.png

    1 #include

    2 #include

    3 using namespacestd;4 intn;5 int a[1100];6 int f[1100];7 intmain()8 {9 scanf("%d",&n);10 for(int i=1;i<=n;++i)scanf("%d",&a[i]);11 for(int i=1;i<=n;++i)12 {13 f[i]=1;14 for(int j=1;j=a[j]&&f[j]+1>f[i])f[i]=f[j]+1;16 }17 int ans=0;18 for(int i=1;i<=n;++i)19 ans=max(ans,f[i]);20 printf("%d",ans);21 return 0;22 }

    View Code

    最长上升子序列代码:

    8f900a89c6347c561fdf2122f13be562.png

    961ddebeb323a10fe0623af514929fc1.png

    1 #include

    2 #include

    3 using namespacestd;4 intn;5 int a[1100];6 int f[1100];7 intmain()8 {9 scanf("%d",&n);10 for(int i=1;i<=n;++i)scanf("%d",&a[i]);11 for(int i=1;i<=n;++i)12 {13 f[i]=1;14 for(int j=1;ja[j]&&f[j]+1>f[i])f[i]=f[j]+1;16 }17 int ans=0;18 for(int i=1;i<=n;++i)19 ans=max(ans,f[i]);20 printf("%d",ans);21 return 0;22 }

    View Code

    233333,如果不仔细看你会以为这2份代码是一样的,仔细看你会发现相似度99%。

    但是窝分不清 的当然不是n^2的求法,而是nlogn的求法,之所以分不清,还是因为窝太弱了,窝用的二分从来都是stl,所以会经常搞混该用lower_bound还是upper_bound qwq

    先来说一下nlogn的求解思想,令f[i]代表长度为i的所有最长不下降子序列的最后一位的最小值是多少。为什么要记录最小是多少那?因为我们想要这个序列最长,那么只有末尾最小才能有更多的数接到它的后面构成一个更长的序列。这时我们就能得到一个性质:f数组是递增的。证明:f[i]代表的是长度为i的最长不下降子序列的结尾最小的数,如果它后面来了一个比它大的数,那么这个数一定能构成至少长度为i+1的最长不下降子序列,所以在f数组里一定不会比它的位置靠前。

    所以开一个变量len来记当前找到的最长不下降子序列有多长了,如果a[i]>=f[len],那么直接放到f[len]后面,并且len++,但是如果a[i]

    有一个值得说明的点是f数组只是用来记录结尾的数的,f数组连起来并不是一个最长不下降子序列

    最长上升子序列也是一样的道理,只不过由于要求严格递增,所以要替换的是大于等于它的第一个数

    唔,二分用的2个stl分别是lower_bound和upper_bound,第一个是求大于等于一个数的第一个数的位置,第二个是求大于一个数的第一个数的位置。

    最长上升子序列nlogn算法:

    8f900a89c6347c561fdf2122f13be562.png

    961ddebeb323a10fe0623af514929fc1.png

    1 #include

    2 #include

    3 #include

    4 using namespacestd;5 intn;6 int a[100005],f[100005];7 intmain()8 {9 scanf("%d",&n);10 for(int i=1;i<=n;++i)scanf("%d",&a[i]);11 f[1]=a[1];int len=1;12 for(int i=2;i<=n;++i)13 {14 if(a[i]>f[len])f[++len]=a[i];15 else{16 int tmp=lower_bound(f+1,f+len+1,a[i])-f;17 f[tmp]=a[i];18 }19 }20 cout<

    View Code

    最长不下降子序列nlogn算法:

    8f900a89c6347c561fdf2122f13be562.png

    961ddebeb323a10fe0623af514929fc1.png

    1 #include

    2 #include

    3 #include

    4 using namespacestd;5 intn;6 int a[100005],f[100005];7 intmain()8 {9 scanf("%d",&n);10 for(int i=1;i<=n;++i)scanf("%d",&a[i]);11 f[1]=a[1];int len=1;12 for(int i=2;i<=n;++i)13 {14 if(a[i]>=f[len])f[++len]=a[i];15 else{16 int tmp=upper_bound(f+1,f+len+1,a[i])-f;17 f[tmp]=a[i];18 }19 }20 cout<

    View Code

    其实相似度也是99%,233333333

    展开全文
  • ====接力dalao完成====对前文的一些补充:首先清楚最长不下降子序列是一个递增但是允许不同位元素相等的序列。而最长上升子序列则是一个单调递增的序列。而两者都是子序列,所以子序列的长度一定小于等于原序列。且...
  • 其实这道题有一个更简单的版本,在左程云写的《程序员代码面试指南》——最长递增子序列 我在简单描述这本书中的这个题之前,我们应该先明确什么是子序列子序列就是一个序列中抽出来的(未必连续),如 1 4 2 8 5...
  • 最长上升子序列:是严格上升的,alower_bound:返回序列中大于等于key值的第一个数比如说序列 1 2 3 4 5,key值为3,使用lower_bound返回第三个数最长不下降子序列:不是严格上升,可以存在多个数相等的情况,用upper...
  • 给定一个长度为\(n\)的序列,求:这个序列最长不下降子序列长度\(s\)。在每个元素只能使用一次时最多能取出多少个长度为\(s\)的不下降子序列。在只有第\(1\)个和第\(n\)个元素能无限次使用(其他元素依然只能使用一次...
  • 最长不下降子序列(LIS)——动态规划求解
  • 最长不下降子序列LIS

    2020-12-16 19:22:30
    最长不下降子序列,英文缩写为 LIS(Longest Increasing Subsequence)。其 定义是,设有由 n 个相同的整数组成的数列,记为: a(1)、a(2)、……、a(n)且 a(i)<>a(j) (i<>j) 例如 3,18,7,14,10,12,...
  • 【题目描述】设有由n(1≤n≤200)n(1≤n≤200)个相同的整数组成的数列,记为:b(1)、b...例中13,16,18,19,21,22,63就是一个长度为7的不下降序列,同时也有7 ,9,16,18,19,21,22,63组成的长度为8的不下降...
  • [蓝桥杯2022初赛A组] 最长不下降子序列(dp + 权值线段树) 100分正解。权值线段树优化线性dp
  • 最长不下降子序列及输出序列

    千次阅读 2020-11-27 20:16:38
    回忆一下,以前学动态规划是的最长不下降子序列,我们是如何地推的呢??? First 2n2^n2n暴力,判断每个是否选择输出最大值。 Second 记忆化搜索,时间复杂度待定。 Third n2n^2n2动态规划,代码如下。 #include<...
  • #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.
  • 小Z希望:通过这一次反转操作,使得这个序列的最长不下降子序列的长度尽可能的大,并想让你输出这个最大值。 一个序列的不下降子序列定义为:对于一个序列(p1,p2,…,pk)满足1≤p1<p2<…<pk≤n(n≤819200)且...
  • 例中13,16,18,19,21,22,63就是一个长度为7的不下降序列,同时也有7 ,9,16,18,19,21,22,63组成的长度为8的不下降序列。 【输入】 第一行为n,第二行为用空格隔开的n个整数。 【输出】 第一行为输出最大个...
  • 动态规划dp:假设有一数组a 为原序列,一数组dp 长为len(a)dp【i】的意思为以 a 结尾的不下降子序列的长度。 1、如何求dp【i】呢? 首先我们给dp赋予初始值1。即代表每一个数据为结尾的子序列的长度都为1(即是...
  • c++实现最长不下降子序列 问题: 在一个数字序列中,找到最长的子序列(可以连续),使得这个子序列是下降(非递减)的。 求出此序列的长度 剖析: 本题使用DP. 状态转移方程 具体怎么弄呢? 请看下面表格 ...
  • 一开始瞬间想到最长上升子序列,因为nnn比较大,所有只能用贪心+二分的O(nlogn)O(nlogn)O(nlogn)复杂度的算法写,然后wa了。 后来想了想,其实不对,例如:1 2 3 3 4,最长上升子序列为4,那么答案只需修改1个,而...
  • 【题目描述】 求给定序列的最长不下降子序列(LIS,Longest Increasing Subsequence...而本题的目标就是要求出给定序列的所有不下降子序列中那个最长不下降子序列的长度。【输入】 第一行为n,表示n个数。 第二行为n..
  • 最长不下降子序列(线性动态规划)    我们知道,递推就是按照递推公式不断往前求解的一个过程,对于当前,只有一个状态描述当前的值。若某些问题并非由一个状态而是由多个状态不断推导,那么这种方法就是动态规划...
  • 对于两个序列,求两个序列的最长不下降子序列并输出路径 首先,我想到的是简单的直接求,开b数组存序列,对于每个元素,如果它大于队尾元素,显然可以直接加,如果不是,那么在序列中找到第一个大于它的数并更新之,...
  • 传统的状态设计便是使用f[n] 表示到达第n位时的最长不子序列。那么转移就是f[n]=max(f[i]+1)其中要求a[i]<=a[n]&&i<=n那么想要使得复杂度比较优,就能通过枚举所有满足条件的i来找到最优解。...
  • 最长不下降子序列详解(一)

    万次阅读 多人点赞 2018-08-28 17:19:58
    由2019年字节跳动第二次笔试开始学习,第一部分参考:最长不下降子序列nlogn以及输出序列,作者Milky-Way 1、最长不下降子序列-复杂度为 对于普通的最长不下降子序列,每个数都要从头开始遍历,复杂度 ,只能处理 ...
  • 我们对于O(n2)O(n^2)O(n2)的最长不下降子序列十分熟悉了。 #include <bits/stdc++.h> using namespace std; int n,ans,a[1005],f[1005]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf...
  • 最长不下降子序列就是4 13,7,9,16,38,24,37,18,44,19,21,22,63,15 最长不下降子序列就是7,9,16,18,19,21,22,63 下面我们来分析一下思路 我们使用一个二维数组s[10][3],每一行的第一个代表个数,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 12,906
精华内容 5,162
关键字:

最长不下降子序列

友情链接: bw150.zip