LIS 51Nod 1134 最长递增子序列

给出长度为N的数组，找出这个数组的最长递增子序列。(递增子序列是指，子序列的元素是递增的）

例如：5 1 6 8 2 4 5 10，最长递增子序列是1 2 4 5 10。

Input

第1行：1个数N，N为序列的长度(2 <= N <= 50000)

第2 - N + 1行：每行1个数，对应序列的元素(-10^9 <= S[i] <= 10^9)

Output

输出最长递增子序列的长度。

Input示例

Output示例

 #include <iostream>

 #include <stdio.h>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 #define N  50010

 int a[N],c[N];

 int n,len=;

 int Find(int x)

 {

     int l=,r=len,mid;

     while(l<=r){

         mid=(l+r)>>;

         if(x>c[mid]) l=mid+;

         else r=mid-;

     }

     return l;

 }

 int  main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++)

         scanf("%d",&a[i]);

     for(int i=;i<=n;i++){

         int k=Find(a[i]);

         c[k]=a[i];

         len=max(len,k);

     }

     printf("%d\n",len);

     return ;

 }

STL 求最长上升子序列：

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cstdio>

 using namespace std;

 #define inf 0x3f3f3f3f

 int dp[];

 int a[];

 int main()

 {

     int n;

     while(scanf("%d",&n) != EOF){

         memset(dp,inf,sizeof(dp));

         for(int i = ;i < n; i++)

             scanf("%d",&a[i]);

         for(int i = ;i < n; i++){

             *lower_bound(dp,dp+n,a[i]) = a[i];

         }

         printf("%d\n",lower_bound(dp,dp+n,inf)-dp);

     }

     return ;

 }

巴特西

LIS 51Nod 1134 最长递增子序列

最新文章

热门文章