NC25148. 饥饿的牛
描述
输入描述
第1行: 一个整数，N
第2..?行: 除了最后一行，每一行都包含恰好20个用空格隔开的整数，依次表 示队伍中从前到后的奶牛的编号。如果N不能整除20，那么最后一行包含的数字不到20个
输出描述
第1行: 输出按照FJ的规定，最多可以挑出的奶牛的数目
示例1
输入:
11 2 5 18 3 4 7 10 9 11 8 15
输出:
7
C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 596K, 提交时间: 2019-07-06 17:17:02
#include<bits/stdc++.h>
using namespace std;
int n,a[5555],dp[5555],l;
int main()
{
cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
dp[++l]=a[1];
for(int i=2;i<=n;++i)
{
if(a[i]>dp[l])
dp[++l]=a[i];
else
*lower_bound(dp+1,dp+1+l,a[i])=a[i];
}
cout<<l;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 5ms, 内存消耗: 616K, 提交时间: 2019-07-07 21:40:10
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<int>v;
for(int i=0,x;i<n;i++)
{
cin>>x;
auto it=lower_bound(v.begin(),v.end(),x);
if(it==v.end()) v.push_back(x);
else *it=x;
}
cout<<v.size()<<endl;
return 0;
}