POJ 2533 Longest Ordered Subsequence

题目描述：LIS（Longest Increasing Subsequence）模板题

分析：O(n^2)的方法

状态表示：d[i]表示以i结尾的最长上升子序列长度

转移方程：d[i]=max{ 1,d(j)+1 } ( j=1,2,3,...,i-1且A[j]<A[i] )

即A[j]<A[i]，d[i]=d[j]+1

A[j]>=A[i],d[i]=1

 #include<cstdio>

 int main()

 {

     int N,a[],d[];

     scanf("%d",&N);

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

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

     int max=;

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

     {

         d[i]=;

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

         {

             if(a[j]<a[i]&&d[j]+>d[i])

             d[i]=d[j]+;

         }

         if(d[i]>max)  max=d[i];

     }

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

     return ;

 }

O(nlogn)的方法：

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int INF=;

 int N,a[],d[],g[];

 int main()

 {

     scanf("%d",&N);

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

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

     for(int i=;i<=N;i++) g[i]=INF;

     int ans=;

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

     {

         int k=lower_bound(g+,g++N,a[i])-g;

         d[i]=k;

         g[k]=a[i];

         ans=max(ans,d[i]);

     }

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

     return ;

 }

巴特西

POJ 2533 Longest Ordered Subsequence

最新文章

热门文章