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


全部评论

相关推荐

06-15 02:05
已编辑
南昌航空大学 数据分析师
Eason三木:你如果想干技术岗,那几个发公众号合唱比赛的经历就去掉,优秀团员去掉,求职没用。然后CET4这种不是奖项,是技能,放到下面的专业技能里或者单独列一个英语能力。 另外好好改改你的排版,首行缩进完全没有必要,行间距好好调调,别让字和标题背景黏在一起,你下面说能做高质量PPT你得展现出来啊,你这简历排版我用PPT做的都能比你做的好。 然后自我评价,你如果要干数据工程师,抗压能力强最起码得有吧。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
07-10 14:08
已编辑
江西农业大学 Java
念旧select:做完把项目放到自己硬盘里给他看,看完拷走
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务