| 比赛 |
动态规划练习2 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
最长上升子序列 |
最终得分 |
100 |
| 用户昵称 |
FFF团 |
运行时间 |
0.003 s |
| 代码语言 |
C++ |
内存使用 |
0.32 MiB |
| 提交时间 |
2017-03-28 18:36:54 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long dp[20000],a[20000];
long long n;
int main(){
freopen("lis1.in","r",stdin);
freopen("lis1.out","w",stdout);
cin>>n;
fill(dp,dp+n+1,0x7fffffff);
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++){
*lower_bound(dp,dp+n,a[i])=a[i];
}
for(int i=n;i>=0;i--)if(dp[i]!=0x7fffffff){
cout<<i+1;
break;
}
fclose(stdin);
fclose(stdout);
return 0;
}