最长上升子序列(LIS)简介

基本概念

从给定的有序序列a[1],a[2],...,a[n]中选取b[1],b[2],...,b[m],其中b[1]< b[2] < b[m],且选出的子序列中在原序列的先后顺序不变。求一种令m最大的取法。即最长上升子序列问题(Longest increasing subsequence)

解法一

定义dp[i]表示以第i个位置的数作为子序列中最后一个元素时,能够构成的子序列的最大长度。转移方程如下:

dp[i]=max(dp[i],dp[j]+1)  j<i&&a[j]<a[i]

这个算法的时间复杂度为O(n^2),能够处理的数据规模有限,但是在计算的过程中能够获得更多的信息,能方便地计算最长子序列和值最长子序列组合个数等问题,并且代码长度也较短:

int maxlen=0;
    for(int i=0;i<n;++i){
        dp[i]=1;//初始值
        for(int j=0;j<i;++j){
            if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1);
        }
        maxlen=max(maxlen,dp[i]);
    }


解法二

对于给定的一个序列,它的最长子序列的长度是固定的。比如第一种解法,每个位置上的数的dp值也是固定的。当计算第i个位置时,只需要从前i-1个数中找到比当前数小且DP值最大的即可。而dp[i]就表示第i个数能够出现在某个子序列中,且所处位置的下标最大的值。因此,现在的目标就是如何快速得到这个值。 可以定义新的动态规划minnum[i],表示在处理当前位置时,由之前元素构成的长度为i的上升序列的最末元素,若有多个长度为i的上升序列,则记录最小的那个最末元素。可知minnum数组是一个递增的数组,对于当前整数a[x],只需在minnum中找到最大的一个比a[x]小的数所在位置j即可,j+1便是a[x]能够出现在所有子序列中的最大位置。而该过程可用二分查找的方式,因此算法复杂度为O(nlog(n))。用maxlen表示当前情况下能构成的最大子序列长度,由于加入一个元素以后,可以构成的最长子序列的长度可能增加,此时需要令maxlen加1。(具体可以参照下面的例2


例1 HDU 1087

题意

从一维棋盘的起点跳到终点,只能从左到右跳,中间有很多棋子,每个棋子都有值。可以选择从起点跳到任意一个棋子,然后从当前位置跳到一个比该棋子值大的棋子的位置;或者从一个棋子跳到终点,当然也可以直接从起点跳到终点。求一种跳法,使得经过的棋子的值之和最大。

思路

对于第i个棋子,可以从起点跳到这个位置,也可以从前面一个比该棋子值小的位置跳过来。定义dp[i]表示跳到第i个位置时能够得到的棋子的值之和,只需找到一个dp值最大的位置j,满足j < i且棋子j的值小于棋子i即可。如果不存在则直接从起点跳到该点。由于任意一步可以选择跳到终点,所以每次计算都需要更新最终结果。

代码示例

#include<bits/stdc++.h>
using namespace std;

long long dp[2000];
long long num[2000];

int main()
{
    int n;
    while(cin>>n,n)
    {
        for(int i=0;i<n;++i) cin>>num[i];
        memset(dp,0,sizeof(dp));
        long long ans=0;

        //枚举每个棋子
        for(int i=0;i<n;++i){
            dp[i]=num[i];
            for(int j=0;j<i;++j){
                //如果当前棋子i比之前的棋子j大,可以从j转移
                if(num[i]>num[j]) dp[i]=max(dp[i],dp[j]+num[i]);
            }
            ans=max(ans,dp[i]);//更新
        }
        cout<<ans<<endl;
    }
    return 0;
}


例2 TOJ 1765

题意

给出一个序列,求出该序列的最长上升子序列。(N<=10000)


思路

定义dp[i]表示处理到当前位置时,之前整数能够构成的长度为i的递增序列中,第i位(最后一位)上数字最小的值(因为这样的长度为i的递增序列可能不唯一)。按顺序从左到右,计算每个数字作为序列最后一个数字,就能够构成最长的序列的长度。


代码示例

#include<bits/stdc++.h>
using namespace std;

int dp[10005];

int main()
{
    int n;
    while(cin>>n)
    {
        dp[0]=0;
        int tail=0;
        int a;
        for(int i=1;i<=n;++i){
            cin>>a;
            //二分
            int low=0,high=tail-1;
            while(low<=high){
                int mid=(low+high)/2;
                if(dp[mid]>=a) high=mid-1;
                else low=mid+1;
            }
            //新加入的数能够使得可得到的最长子序列长度增加
            if(low>=tail) tail++;
            dp[low]=a;
        }
        cout<<tail<<endl;
    }
    return 0;
}


上一篇:   HDU 1950(LIS)

下一篇:   多重背包简介



评论

登录之后就可以评论 / 回复啦(#^.^#)    点此登录    点此注册

评论列表

暂无评论!快写一条吧(๑′ᴗ‵๑)