欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【动态规划】最长上升子序列及其相关思想

程序员文章站 2022-06-10 19:37:21
...

最长上升子序列



最长上升子序列


总时间限制:  2000ms  内存限制:  65536kB


描述


一个数的序列bi,当b1 < b2 < ... < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1a2, ..., aN),我们可以得到一些上升的子序列(ai1ai2, ..., aiK),这里1 <= i1 < i2 < ... < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8).你的任务,就是对于给定的序列,求出最长上升子序列的长度。


输入


输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到10000。


输出


最长上升子序列的长度。


样例输入


7
1 7 3 5 9 4 8


样例输出


4


思想:

【动态规划】最长上升子序列及其相关思想

         对每一个数遍历一遍,到某个数时,对其之前的数再遍历比较,例如,1之前没有数,则最大序列为1(自身),7之前有1,1<7,显然,1,7是递增的,所以7的最大序列是2,3之前,7>3,不能构成,1<3,递增,故3的最大序列是2,5之前有,3<5,此时已经知道3之前是有1了,3的最长序列是2,所以5的最长序列只要自身加上3的就行了,即为3,9之前有5,最长为5的最长序列加上自身,即为4,此时7<9,但7的最长序列是2<5的最长序列,所以取4,后面以此类推···


【解题】

#include<iostream>
using namespace std;
#define N 1001
int lis(int c[],int n)
{
	int i,j;
	int b[N];
	b[0]=1;
	for(i=1;i<n;i++)
	{
		b[i]=1;
		for(j=i-1;j>=0;j--)
		{
			if(c[i]>c[j]&&b[i]<=b[j])
				b[i]=b[j]+1;
		}
	}
	for(i=j=0;i<n;i++)	//j为最大值
	{
		if(b[i]>j)
			j=b[i];
	}
	return j;
}
int main()
{
	int i,n,c[N];
	cin>>n;
	for(i=0;i<n;i++)
	{
		cin>>c[i];
	}
	cout<<lis(c,n)<<endl;
	return 0;
}


【实现】

#define N 200		//范围
int lis(int c[],int n) 
{
	int i,j,max; 
	int b[N];
	b[0]=1;
	for(i=1;i<n;i++) 
	{
		b[i]=1;				//算上自身
		for(j=i-1;j>=0;j--)		//对当前的数,对之前的数遍历比较
		{ 
			if(c[i]>c[j]&&b[i]<=b[j])	//找到比自身小的,则相应的数+1
				b[i]=b[j]+1; 
		} 
	} 
	for(i=1,max=b[0];i<n;i++)	//查找最大值
	{ 
		if(b[i]>max) 
			max=b[i]; 
	} 
	return max;
}


                                                             “玲珑杯”ACM比赛 Round #19


                                                B -- Buildings


                                                                                      Time Limit:2s Memory Limit:128MByte




【题目大意】

描述

这有n座建筑排在这里,并且第i座房子的高度是hi,若在[l,r]这段连续间隔的建筑中有max(hl,,hr)min(hl,,hr)kmax(hl,…,hr)−min(hl,…,hr)≤k.则称这段是和谐的。现在请你计算这和谐间隔的数量。


输入

第一行包含2个整数n(1n2×105),k(0k109)n(1≤n≤2×105),k(0≤k≤109),第2行包含n个整数hi(1hi109)hi(1≤hi≤109)


输出

输出为一行,答案的数量


提示

Harmonious intervals are:[1,1],[2,2],[3,3],[1,2],[2,3][1,1],[2,2],[3,3],[1,2],[2,3].



【思想】

        对每个数遍历一次,遍历时对当前的这个数与前面的数对比,对于每个数初始化最大值和最小值都是自身,同时求这段连续的数字的最大值和最小值,例如样例中,k=1,设count是总数,count=0,从1开始,1<=k,成立,count=1,[1,1];前面没数了,遍历完毕。对于2,max=min=2,max-min<k成立,count=2,[2,2]再往前,1<2,min=1,max-min=1<=k成立,count=3,[1,2],对于3,max=min=3,成立,count=4,[3,3],往前走,min=2,max=3,max-min<=k成立,count=5,[2,3],到1,min=1,max=3,max-min=2>k,不成立。所以总数为5。

       再例如2,1,3,5,4,k=2,从2开始,max=min=2,成立count=1,[2,2],对于1,自身成立,count=2,[1,1],往前走,到2,max=2.min=1,max-min=1<=k成立,count=3,[2,1],对于3,自身成立,count=4,[3,3],往前走,到1,max=3,min=1,max-min=2<=k成立,count=5,[1,3],往前到2,显然成立,count=6,[2,1,3]。对于5,自身成立count=7,[5,5],往前走,到3,max=5,min=3,max-min=2<=k,成立,count=8,[3,5],往前走,到1,max=5,min=1,max-min=4>k,不成立,结束遍历。理由:无论再怎么往前走,max只会越来越大,min只会越来越小,所以max-min的值会拉大,一定比k大。后面的同理。


【解题】


#include<iostream>
using namespace std;
#define maxsize 200005
int a[maxsize];
int f(int a[],int n,int k)
{
	int count=0,i,j,max,min;
	for(i=0;i<n;i++)
	{
		for(j=i-1,max=min=a[i];j>=0;j--)
		{
			max=max>a[j]?max:a[j];
			min=min<a[j]?min:a[j];
			if(max-min<=k)
				count++;
			else
				break;
		}
	}
	return count+n;
}
int main()
{
	int n,k,i;
	while(cin>>n>>k)
	{
		for(i=0;i<n;i++)
			cin>>a[i];
		cout<<f(a,n,k)<<endl;
	}
	return 0;
}

相关标签: ACM OJ题目