最長非降子序列模型（poj1088）

1)首先最長單調非增子序列(一維)

描述：

給定一整型數列{a₁,a₂...,a_n}（0

如：1 9 10 5 11 2 13的最長單調遞增子序列是1 9 10 11 13，長度為5。

題目鏈接：http://acm.nyist.net/JudgeOnline/problem.php?pid=17點擊打開鏈接

方法1：

運用轉移方程 dp【i】=max（dp【j】）+1 ( j < i 且a [ i ] > a[ j ])

意思就是當前選擇是在前面滿足條件的基礎上最大的值，然後+1

代碼：

#include
#include
#include
#include
#define N 10010
using namespace std;

int dp[N];
char s[N];

int main()
{
    int len,test,i,j,max;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%s",&s);
        len=strlen(s);
        dp[0]=1;
        int ans=1;
        for(i=1;i=0;j--)
            {
                if(s[i]>s[j]&&maxans)
                ans=dp[i];
        }
        printf("%d\n",ans);
    }
    return 0;
}

運用二分查找，如果後一個值比已有的遞增序列的最後一個大，那麼可以放在後面使得序列長度+1，否則二分查找找出位置，把比它大的值更新小，這樣下次插入的時候能夠插入更多的值，時間復雜度較低!

詳細分析：http://blog.csdn.net/y990041769/article/details/8544081

代碼：

 
#include 
#define INF 0x7fffffff
int n;
int a[100005];
int d[100005];
int len;
int Find(int L,int R,int ob)
{
    while(L<=R)
    {
        int mid=(L+R)/2;
        if(d[mid]==ob)
            return mid;
        else if(d[mid]d[len])
                j=++len;
            else
                j=Find(1,len,a[i]);
            d[j]=a[i];
        }
        printf("%d\n",len);
    }

}
        

2）二維求一個最長遞增序列

描述：

從任意一點開始，每次可以選擇四周相鄰的點且比他值小的走，每個點只能走一次，求走出來的一個最長的序列。

題目鏈接：滑雪

分析：按照最長單調遞增子序列的思想

首先把它的圖轉化存入一個結構體中，存入行，列，以及值，按值的大小從小到大排序，同樣運用前面的轉移方程運用轉移方程 dp【i】=max（dp【j】）+1 ( j < i 且a [ i ] > a[ j ])

注意點：每次只能走相鄰的點。所以一定判斷好，在這邊wa了、

代碼：

#include 
#include 
#include 
#include 
const int N =120;
struct Node
{
    int x,y;
    int h;
};
Node a[N*N];
int map[N][N];

int comp(Node a,Node b)
{
    if(a.h!=b.h)
        return a.h=0;j--)
            {
                if(abs(a[i].x-a[j].x)==1 && abs(a[i].y-a[j].y)==0 && a[i].h>a[j].h && dp[j]>tmp )  //沒有搞清楚關系
                    tmp=dp[j];
                if(abs(a[i].y-a[j].y)==1 && abs(a[i].x-a[j].x)==0 && a[i].h>a[j].h && dp[j]>tmp)
                    tmp=dp[j];
            }
            dp[i]=tmp+1;
            //printf("%d ",dp[i]);
            if(dp[i]>max)
                max=dp[i];
        }
        printf("%d\n",max);
    }
    return 0;
}