菜鸡的题解021——拦截导弹

最长不上升子序列和最长上升子序列的典型题目！

参考代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<set>
#include<sstream>
#include<cstring>
#include<utility>
using namespace std;
typedef long long ll;
typedef long l;
const int N = 11000;
int a[N],f[N],ans=1;
int main(){
	int i,n;
	for(i=1;~scanf("%d",&a[i]);i++);
	n=i-1;
	for(i=1;i<=n;i++)f[i]=1;
	for(i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[j]>=a[i])f[i]=max(f[i],f[j]+1);
		}
		ans=max(ans,f[i]);
	}
	cout<<ans<<endl;
	ans=1;
	for(i=1;i<=n;i++)f[i]=1;
	for(i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[j]<a[i])f[i]=max(f[i],f[j]+1);
		}
		ans=max(ans,f[i]);
	}
	cout<<ans;
}