LIS入門1

早都想寫關于LIS的部落格了，可是一直苦于自己不能了解它，是以拖到現在才寫。

現在我們先來簡單的介紹一下什麼是LIS，LIS（Longest Increasing Subsequence）最長上升子序列，LIS也是簡單的動态規劃問題吧。

什麼是最長上升子序列呢？現在我們先随便給一個序列吧。例如：1 7 3 5 9 4 8，他的上升的子序列有好多個例如：1 3 5,1 3 5 9，

1 3 8，但是我們要求的是它的最長的上升子序列，或許最長上升的子序列的個數不止一個，但是最長子序列的長度一定是一個定值吧！我們要求的就是這個最長子序列的長度。

對于求LIS我們有兩種方法，一種是複雜度為O(N^2)做法，還有一種複雜度為O(NlogN)做法，在這裡我們先學習第一種方法。

O(N^2)做法：dp動态規劃：

我們還是用 1 7 3 5 9 4 8這個序列，我們讓a[]={1,7,3,5,9,4,8}我們的大緻思路就是我們先找以a[0]結尾的LIS，然後再找以a[1]結尾的LIS，以此類推，然後我們從這7個LIS中選擇最大的那個，最大的那個就一定是我們要找的這個序列的LIS。我們讓dp[i]代表以a[i]結尾的LIS。

我們來模拟一下整個過程，首先我們應該讓dp[i]=1.因為每個單獨的一個數字他的LIS就是1，然後我們開始：

首先我們看以a[0]結尾的LIS，這毫無疑問，肯定等于1對吧，是以此時dp[0]=1;

然後看a[1],因為a[1]>a[0],是以dp[1]=dp[0]+1;dp[1]=2;

再看a[2],我們先從a[0]開始看，因為 a[2]>a[0]，是以dp[2]=dp[0]+1;dp[2]=2;再看a[1],因為  a[2]<a[1],是以不做處理。dp[2]=2。

再看a[3],我們還是先從我們先從a[0]開始看，因為 a[3]>a[0]，是以dp[3]=dp[0]+1;dp3]=2;再看a[1],因為  a[23]<a[1]是以不做處理，接着看a[2],，因為 a[3]>a[2]，是以dp[3]=dp[2]+1;dp3]=3;現在我們得到了兩個dp[3]，那麼dp[3]到底等于幾呢？首先我們要知道我們求得是最長的序列，是以說呢？我們當然要選最大的啊，是以dp[3]=max(2,3),是以dp[3]=3；

下面一次類推，從中我們就可以推出狀态轉移：dp[i]=max(dp[i], dp[j]+1) (0<=j< i, a[j]< a[i]) 。

下面給一道例題來闡述代碼的具體寫法：

某國為了防禦敵國的飛彈襲擊,發展出一種飛彈攔截系統.但是這種飛彈攔截系統有一個缺陷:雖然它的第一發炮彈能夠到達任意的高度,但是以後每一發炮彈都不能超過前一發的高度.某天,雷達捕捉到敵國的飛彈來襲.由于該系統還在試用階段,是以隻有一套系統,是以有可能不能攔截所有的飛彈. 

怎麼辦呢?多搞幾套系統呗!你說說倒蠻容易,成本呢?成本是個大問題啊.是以俺就到這裡來求救了,請幫助計算一下最少需要多少套攔截系統. 

Input

輸入若幹組資料.每組資料包括:飛彈總個數(正整數),飛彈依此飛來的高度(雷達給出的高度資料是不大于30000的正整數,用空格分隔) 

Output

對應每組資料輸出攔截所有飛彈最少要配備多少套這種飛彈攔截系統. 

Sample Input

8 389 207 155 300 299 170 158 65
           

Sample Output

2
           

 這個題翻譯過來就是看給的序列中有幾個連續的不下降的子序列，其實這個就等于求LIS，下面給出LIS代碼。

#include<stdio.h>
#include<stdio.h>
#include<iostream>
using namespace std;
int a[1003];//用于存放所給的序列
int dp[1003];//表示以i結尾的LIS
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            dp[i]=1;//對dp進行初始化。使得剛開始的LIS為一個數字的LIS  1‘
        }
        int ans=0;
        for(int i=2;i<=n;i++)//以每一個數字結尾時求此時的的LIS
        {
            for(int j=1;j<i;j++)
            {
                if(a[j]<a[i])
                    dp[i]=max(dp[i],dp[j]+1);//求最大值
            }
            ans=max(ans,dp[i]);//找到那個最大的LIS
        }
        printf("%d\n",ans);
    }
    return 0;
}