最长降落序列——中高级

最长下降序列——中高级

Description

给你一串整数，从左到右按顺序挑出一些数字，构成严格下降序列，问最长能构成多长
如6个数4 5 2 4 2 2，那么最长可以挑出5 4 2，长度为3

Input

首先输出T（T<=50），表示有T组数据。
每组数据：
首先输入n表示有几个数(1<n<10000)。
后面一行跟着n个整数

Output

对于每个样例输出一个数字，表示最长的长度

Sample Input


1
6
4 5 2 4 2 2

Sample Output



3
这题可以当模板用，用了单调队列的思想。
模板1：严格下降子序列

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
int a[10006],dp[10006];
int find(int l,int r,int x)
{
	int mid;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(dp[mid]>x)l=mid+1;
		else if(dp[mid]<x)r=mid-1;
		else return mid;
	}
	return l;
}

int main()
{
	int n,m,i,j,T,len,k;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		memset(dp,0,sizeof(dp));
		len=0;
		for(i=1;i<=n;i++){
			scanf("%d",&a[i]);
			if(len==0){
				dp[++len]=a[i];continue;
			}
			if(a[i]<dp[len]){
				dp[++len]=a[i];continue;
			}
			k=find(1,len,a[i]);
			dp[k]=a[i];
		}
		/*for(i=1;i<=len;i++){
			printf("%d ",dp[i]);
		}
		printf("\n");*/
		printf("%d\n",len);
	}
	return 0;
}

模板2：不上升子序列（非严格）
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
int a[10006],dp[10006];
int find(int l,int r,int x)
{
	int mid;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(dp[mid]>=x)l=mid+1;
		else if(dp[mid]<x)r=mid-1;
	}
	return l;
}

int main()
{
	int n,m,i,j,T,len,k;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		memset(dp,0,sizeof(dp));
		len=0;
		for(i=1;i<=n;i++){
			scanf("%d",&a[i]);
			if(len==0){
				dp[++len]=a[i];continue;
			}
			if(a[i]<=dp[len]){
				dp[++len]=a[i];continue;
			}
			k=find(1,len,a[i]);
			dp[k]=a[i];
		}
		for(i=1;i<=len;i++){
			printf("%d ",dp[i]);
		}
		printf("\n");
		//printf("%d\n",len);
	}
	return 0;
}

最长降落序列——中高级

相关推荐