POJ 拦截导弹

这道题是最长上升子序列的变形题 AC代码 最长上升子序列的枚举对象是每一个a[i]为终点的上升子序列，之后在a[i]前面的序列里找到最长的上升子序列。 递推式： Maxlen[1]=1; Maxlen[k]=Max{Maxlen(for i (1<i<k) ) }+1 Maxlen[k]指的就是以k为下表的数组元素为终点的最大上升子序列的长度。

#include<bits/stdc++.h>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
const int N =1e5+5;
int n;
struct cmp {
	bool operator()(const int&a,const int&b) const {
		return a>b;
	}
};
//int month[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31};
int a[30];
int b[30];
int main() {
	cin >>n;
	for(int i =1;i<=n;i++){
		cin >>a[i];
	}
	b[1]=1;
	for(int i =2;i<=n;i++){
		int temp = 0;
		for(int j =1;j<i;j++){
			if(a[i]<=a[j])
			{
				if(temp<b[j])
				temp = b[j];
			}
		}
		b[i]=temp+1;
		//cout<<b[i]<<" ";
	}
	int ans =-1;
	for(int i =1;i<=n;i++){
		if(ans <b[i])
		{
			ans = b[i];
		}
	}
	cout<<ans<<endl;
	return 0;
}
//3
//203  200  300