题目分析
不写了,这个写的详细 传送门
C++代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>l,a;//l用来记录最长上升序列和最长不上升序列
int main()
{
int x;
while(cin>>x) a.push_back(x);
//先计算第二问,求需要几套系统,即求最大上升子序列
//lower_bound函数找到大于或等于*t的第一个数的位置
for(auto t=a.begin();t<a.end();t++)
{
auto it=lower_bound(l.begin(),l.end(),*t);
if(it==l.end()) l.push_back(*t);//如果数组中没有比这个数大或者相等的数就将这个数添加到数组中
else *it=*t;//否则,替换
}
//记录第二问的的结果
int len=l.size();
//清空记录所用数组
l.clear();
//翻转a数组,用来求第一问
reverse(a.begin(),a.end());
//求第二问,最长不上升子序列的长度
//upper_bound函数找到大于*t的第一个数的位置 ,和lower还是有区别的
for(auto t=a.begin();t<a.end();t++)
{
auto it=upper_bound(l.begin(),l.end(),*t);
if(it==l.end()) l.push_back(*t);//如果数组中没有比这个数大的数就将这个数添加到数组中
else *it=*t;//否则,替换
}
cout<<l.size()<<endl<<len<<endl;
return 0;
}