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

最长上升子序列

最长上升子序列

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

描述

一个数的序列b_i，当b₁ < b₂ < ... < b_S的时候，我们称这个序列是上升的。对于给定的一个序列(a₁, a₂, ..., a_N)，我们可以得到一些上升的子序列(a_i1, a_i2, ..., a_iK)，这里1 <= i₁ < i₂ < ... < i_K <= 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({}^{},\dots ,{}^{})-min({}^{},\dots ,{}^{})\le k$.，则称这段是和谐的。现在请你计算这和谐间隔的数量。

输入

第一行包含2个整数$n(1\le n\le 2\times {}^{}),k(0\le k\le {}^{})$，第2行包含n个整数${}^{}(1\le {}^{}\le {}^{})$

输出

输出为一行，答案的数量

提示

Harmonious intervals are:$[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;
}