社区讨论

帮者必关

xxuxiyou
B3637最长上升子序列参与者 5已保存回复 12

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@mm8jpmsk
此快照首次捕获于
2026/03/02 10:14
上周
此快照最后确认于
2026/03/04 21:50
6 天前
查看原帖
Input 第一行输入一个整数n 第二行输入n个正整数，分别表示a_1,a_2…a_n
Output 第一行最长上升子序列的长度
接下来输出若干个数,表示具体的子序列,使用空格分隔 如果有多组可行解,输出字典序最小的解方案 //题目被改了一下，要求还要输出最长上升子序列 如： 输入
5
2 3 4 1 2
输出
4
1 3 4 8
我的有问题代码：
CPP
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> a;
vector<int> f;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i = 0;i<n;i++){
		int x;cin>>x;
		a.push_back(x);
	}
	f.push_back(a[0]);
	for(int i = 1;i<n;i++){
		if(a[i]>f.back()){
			f.push_back(a[i]);
		}
		else{
			int x = lower_bound(f.begin(),f.end(),a[i])-f.begin();
			f[x] = a[i];
		}
	}
	cout<<f.size()<<endl;
	for(int i = 0;i<f.size();i++)cout<<f[i]<<" ";
}

回复

共 12 条回复，欢迎继续交流。

正在加载回复...