序列上的一些文章

主要谈两个

LCS

见dp->最长公共子序列

http://blog.csdn.net/wu_tongtong/article/details/76998351

LIS

主要介绍nlogn算法

g[]=num[];  //长度为1的最小 
    //f[1]=1;  写完会发现f可有可无 
    int t=;  //当前最长上升子序列的长度 
    for (i=;i<=n;i++)
    {
        int l=,r=t,mid;
        while (l<=r)
        {
            mid=(l+r)>>;
            if (g[mid]<num[i])  //找到小于a[i]的最大的一个 
               l=mid+;  //mid+1  不知不觉就+1 
            else r=mid-;
        }
        g[l]=num[i]; //l就是长度 
        //f[i]=l;
        if (l>t) t=l;
    }
    return t;  //最长上升子序列长度
           

那要是最长不降怎么办呢

int le=;
    f[]=a[];
    for (i=;i<=n;i++)
    {
        if (a[i]>=f[le]) f[++le]=a[i];   //直接接上
        else  f[upper_bound(f+,f++le,a[i])-f]=a[i];
        //upper_bound  >的第一个数 
    }
    return le;
           

大佬的码风，果然优美，这就激发我yy一种LIS的stl写法

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

int n;
int g[];

int main()
{
    scanf("%d",&n);
    int len=;
    for (int i=;i<=n;i++) 
    {
        int u;
        scanf("%d",&u);
        if (i==) 
        {
            g[]=u;  //g单调不减 
            continue;
        }
        if (u>g[len]) g[++len]=u;
        else g[lower_bound(g+,g++len,u)-g]=u;
        //lower_bound  >=的第一个 
    }
    printf("%d",len);
}