百练2757:最长上生子序列题解

2757:最长上升子序列

查看提交统计提示提问 总时间限制:  2000ms  内存限制:  65536kB 描述 一个数的序列 b_i，当 b₁ <  b₂ < ... <  b_S的时候，我们称这个序列是上升的。对于给定的一个序列( a₁,  a₂, ...,  a_N)，我们可以得到一些上升的子序列( a_i1,  a_i2, ...,  a_iK)，这里1 <=  i₁ <  i₂ < ... <  i_K <= N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8). 你的任务，就是对于给定的序列，求出最长上升子序列的长度。 输入 输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。 输出 最长上升子序列的长度。 样例输入 7 1 7 3 5 9 4 8 样例输出 4 来源 翻译自 Northeastern Europe 2002, Far-Eastern Subregion 的比赛试题

查看  提交  统计  提示  提问 代码： #include<cstdio> #include<algorithm> using namespace std; #define MAX 1002 int arr[MAX], b[MAX]; //b[len]表示最长递增子序列长度为len的最小的a[i] int LIS(int n){ int len = 1; b[1] = arr[1]; for(int i = 1; i <= n; ++i){ if(arr[i] > b[len]){ b[++len] = arr[i]; }else{ int pos = lower_bound(b + 1, b + len + 1, arr[i]) - b; b[pos] = arr[i]; } } return len; } int main(){ int n; scanf("%d", &n); for(int i = 1; i <= n; ++i){ scanf("%d", &arr[i]); } printf("%d\n", LIS(n)); return 0; }