序列上的一些文章

主要談兩個

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);
}