题解 P3970 【[TJOI2014]上升子序列】

· · 题解

LIS（Longest Increasing Subsequence）最长上升子序列 或者 最长不下降子序列。

很基础的题目，有两种算法，复杂度分别为O(n*logn)和O(n^2) 。

安利原地址https://blog.csdn.net/zhangyx_xyz/article/details/50949957

先回顾经典的

O(n^2)

的动态规划算法:

设a[t]表示序列中的第t个数，dp[t]表示从1到t这一段中以t结尾的最长上升子序列的长度，初始时设dp[t] = 0(t = 1, 2, ..., len(A))。则有动态规划方程：dp[t] = max{1, dp[j] + 1} (j = 1, 2, ..., t - 1, 且a[j] < a[t])。

一般若从a[t]开始，此时最长不下降子序列应该是按下列方法求出的： 在a[t+1],a[t+2],...a[n]中，找出一个比a[t]大的且最长的不下降子序列，作为它的后继。

代码实现如下：


#include<iostream>
using namespace std;
#define max(a,b) a>b?a:b
int main()
{
    int n, i, j, dp[101], x[101], max_len;
    while (cin >> n)
    {
        for (i = 0; i < n; i++)
            cin >> x[i];
        dp[0] = 1;//表示以x[0]为子序列最右边的长度位1
        for (i = 1; i < n; i++)
        {
            dp[i] = 1;//初始化每种情况最小值为1
            for (j = 0; j < i; j++)
            {
                if (x[i]>x[j] && dp[j] + 1>dp[i])//从0-i进行扫描,查找边界小于当前最优解长度相等的解优化最优解
                    dp[i] = dp[j] + 1;//如果允许子序列相邻元素相同  x[i]>=x[j]&&dp[j]+1>dp[i];
            }
        }
        for (i = max_len = 0; i < n; i++)
            max_len = max(max_len, dp[i]);//等到最大子序列长度
        cout << max_len << endl;
    }
    return 0;
}

最长上升子序列

O(nlogn)

解法

在一列数中寻找一些数，这些数满足：任意两个数a[i]和a[j]，若i<j，必有a[i]<a[j]，这样最长的子序列称为最长递增子序列。

设dp[i]表示以i为结尾的最长递增子序列的长度，则状态转移方程为：

dp[i] = max{dp[j]+1}, 1<=j<i,a[j]<a[i].

考虑两个数a[x]和a[y]，x<y且a[x]<a[y],且dp[x]=dp[y]，当a[t]要选择时，到底取哪一个构成最优的呢？显然选取a[x]更有潜力，因为可能存在a[x]<a[z]<a[y]，这样a[t]可以获得更优的值。在这里给我们一个启示，当dp[t]一样时，尽量选择更小的a[x].

按dp[t]=k来分类，只需保留dp[t]=k的所有a[t]中的最小值，设g[k]记录这个值，g[k]=min{a[t],dp[t]=k}。

这时注意到g的两个特点（重点）：

  1. g[k]在计算过程中单调不升；

  2. g数组是有序的，g[1]<g[2]<..g[n]。

利用这两个性质，可以很方便的求解：

(1).设当前已求出的最长上升子序列的长度为len（初始时为1），每次读入一个新元素x：

(2).若x>g[len]，则直接加入到d的末尾，且len++；（利用性质2）

否则，在g中二分查找，找到第一个比x小的数g[k]，并g[k+1]=x，在这里x<=g[k+1]一定成立（性质1,2）。

代码实现如下：

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 50001;
int binary_search(int key, int *g, int low, int high)
{
    while (low < high)
    {
        int mid = (low + high) >> 1;
        if (key >= g[mid])
            low = mid + 1;
        else
            high = mid;
    }
    return low;
}
int main()
{
    int i, j, a[maxn], g[maxn], n, len;
    while (cin >> n)
    {
        memset(g, 0, sizeof(g));
        for (i = 0; i < n; i++)
            cin >> a[i];
        g[1] = a[0], len = 1;//初始化子序列长度为1，最小右边界
        for (i = 1; i < n; i++)
        {
            if (g[len] < a[i])//(如果允许子序列相邻元素相同 g[len]<=a[i],默认为不等）
                j = ++len; //a[i]>g[len],直接加入到g的末尾,且len++
            else
                j = binary_search(a[i], g, 1, len + 1);
            g[j] = a[i];//二分查找,找到第一个比a[i]小的数g[k],并g[k+1]=a[i]
        }
        cout << len << endl;
    }
    return 0;
}

例题https://www.luogu.org/problemnew/show/P1108