Description

有 N 辆列车,标记为 1,2,3,…,N。它们按照一定的次序进站,站台内共有 K 个轨道,轨道遵从 先进先出 的原则。列车进入站内的轨道后可以等待任意时间后出站,且所有列车不可后退。现在要使出站的顺序变为 N,N−1,N−2,…,1,询问 K 的最小值是多少。
例如上图中进站的顺序为 1,3,2,4,8,6,9,5,7,则出站的顺序变为 9,8,7,6,5,4,3,2,1。

Input

输入共两行。
第一行包含一个正整数 N ,表示 N 辆列车。
第二行包含 N 个正整数,为 1 至 N 的一个排列,表示进站次序。

Output

输出共一行,包含一个整数,表示站台内轨道数 K 的最小值。

Sample Input

#1
3
1 2 3

#2
9
1 3 2 4 8 6 9 5 7

Sample Output

#1
3

#2
5

Hint

对于 30% 的数据,N≤10;
对于 70% 的数据,N≤2000;
对于 100% 的数据,N≤10^5。

Source

2019NOIP前训练

思路

求最长上升子序列(LIS上升子序列指的是对于任意的i<j都满足ai<aj的子序列)

代码(70分—超时)

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=100010;

int n,ans=-1;
int a[N],dp[N];

int main () {
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	for(int i=1; i<=n; i++) {
		dp[i]=1;
		for(int j=1; j<i; j++)
			if(a[j]<a[i])
				dp[i]=max(dp[i],dp[j]+1);
		ans=max(dp[i],ans);
	}
	printf("%d\n",ans);
	return 0;
}

 AC代码—优化

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=100010;

int n,ans,a[N],v[N],s[N];

int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]);
	for(int i=1; i<=n; i++) {
		if(v[i]==1)
			continue;
		bool flag=false;
		for(int j=1; j<=ans; j++)
			if(a[i]<s[j]) {
				s[j]=a[i];
				v[i]=1;
				flag=true;
				break;
			}
		if(!flag)
			s[++ans]=a[i];
	}
	printf("%d\n",ans);
	return 0;
}
01-02 08:34