最长上升子序列

LIS，LCS算法前置母题

最长上升子序列Ⅰ

动态规划\(O(n^2)\)

以倒数第二个数进行集合划分。

  • 状态表示
    • 集合定义
      所有以第\(i\)个数结尾的上升子序列
    • 属性
      Max
  • 集合划分
    • 当前只有第\(i\)个数，\(f[i] = 1\);
    • 存在比当前数小的情况，\(f[i] = max(f[i], f[j]+1),j\in(0,1,2,3\ldots,i-1)\)

Code

for (int i = 1; i <= n; ++i)
{
    f[i] = 1;
    for (int j = 0; j < i; ++j)
        if (w[j] < w[i]) 
            f[i] = max(f[i], f[j]+1);
}
int res = -1;
for (int i = 1; i <= n; ++i)
    res = max(res, f[i]);

最长上升子序列Ⅱ

贪心+二分\(n\log_{2}^{n}\)

先上大佬233的代码

vectorstk;//模拟堆栈
    stk.push_back(arr[0]);

    for (int i = 1; i < n; ++i) {
        if (arr[i] > stk.back())
            stk.push_back(arr[i]);
        else
            *lower_bound(stk.begin(), stk.end(), arr[i]) = arr[i];
    }
    cout << stk.size() << endl;

此处的的栈的定义不是真正的最长上升子序列，而是长度为\(i\)的上升子序列中，末尾元素最小是栈顶元素。对于一个递增子序列，我们希望末端元素越小越好，这样我们后续可接的数的范围也就越广，可以使得长度更长。

贪心思想

  • 性质
    随着递增子序列的长度增加，末尾元素最小值一定也是严格单调递增的。
  • 证明
    假设两个递增子序列长度为\(x,y且x < y\)，二者末尾元素相同。那么在长度为\(y\)的递增子序列中，末尾元素一定小于倒数第二个元素，那么倒数第二个元素也同时小于长度为\(x\)的递增子序列中的末尾元素，那么就和性质矛盾了，因为我们存储的是长度为\(i\)的上升子序列中，末尾元素最小是栈顶元素。

扩展

怪盗基德的滑翔翼

问题：求最长上升子序列和最长下降子序列。

思路

求解最长上升子序列是从左到右，现在要求最长下降子序列，可以逆序求一个最长上升子序列，自右向左的最长上升子序列就是对自左向右的最长下降子序列。

Code

w[n + 1] = 0;
for (int i = n; i; -- i) {
    for (int j = n + 1; j > i; -- j) {
        if (w[i] > w[j]) f_dw[i] = max(f_dw[i], f_dw[j] + 1);
            }
    }

最大上升子序列和

思路

将集合属性从长度的最大值变成子序列和的最大值。

Code

int res = -1;
for (int i = 1; i <= n; ++i) {
    f[i] = a[i];
    for (int j = 1; j < i; ++j)
        if (a[i] > a[j]) f[i] = max(f[i], f[j] + a[i]);
    res = max(res, f[i]);
}

登山

问题：求以\(i\)为转折点的，两边最长上升子序列和最长下降子序列的长度之和的最大值。

思路

基于怪盗基德的滑翔翼一题，正反两边做一次最长上升子序列，然后二者以\(i\)为转折点求和取最大值即可。

Code

此处不再重复两遍求解子序列过程。

for (int i = 1; i <= n; ++i)
        res = max(res, f[i] + f2[i] - 1);
// 减去1是因为i处二者有重复。

合唱队形

问题：求总人数减去以\(i\)为转折点的，两边最长上升子序列和最长下降子序列的长度之和的最大值的最小值。

思路

同登山问题一样，预处理出每个点的最长上升子序列和最长下降子序列，二者求和取最大值。代码不再重复。

拦截导弹

问题：求最长不上升子序列长度和原序列最少可以划分多少个不上升子序列。

问题分析

对于最长不上升子序列不再赘述。本题难点在于至少用几个不上升子序列可以完全覆盖原序列。

思路(基于贪心)

定义一个数组\(q\)，数组的长度即为不上升子序列个数，数组里存放每一个不上升子序列的最后一个数。
遍历原序列，对于原序列中的每一个数，我们进行以下判断

  1. 如果\(q\)数组中没有一个数比该数大，则新建一个组，存放该数。
  2. 如果1不成立则寻找\(q\)数组中找到大于等于该数的最小值，进行替换。

相关证明

  1. 数组\(q\)是一个单调增序列
    将数组\(q\)视作一个集合，初始状态为空集，数值大小和长度都为0，当我们遍历原数组中每一个元素\(x\)，一定存在不等关系\(c>x>=a>=b\),将\(x\)替换掉\(q\)中的\(a\)元素，单调性并不改变。
    此外每一步都会在集合里寻找一个较小的尾数将其替换掉，若没有比它小的数，则新增一个最大元素，所以数组\(q\)随着下标增大，存储的值也不断增大，故为单调增序列。
  2. 贪心的正确性
    调整法，具体证明单独题解，这里不进行展开。

Code

int res = 0, cnt = 0;
    for (int i = 0; i < n; i++) {
        f[i] = 1;
        for (int j = 0; j < i; j++)
            if (w[i] <= w[j]) f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
        
        int k = 0;
        while (k < cnt && q[k] < w[i]) k++;
        if (k == cnt) q[cnt++] = w[i];
        else q[k] = w[i];
    }

导弹防御系统

问题：至少需要多少个上升子序列和下降子序列才能够完全覆盖原数组。

区别拦截导弹

拦截导弹求解的子序列都是单调不上升子序列，本题是上升子序列和不上升子序列都有，二者组合起来求一个子序列总数的最小值。

问题分析

对于原序列中的每一个数\(x\)，无外乎两种可能性，接在某段上升子序列中或者接在某段非上升子序列中，产生新的子序列，该子序列的产生又会对后续数的两种可能性造成影响，不断持续下去进而对答案造成影响，形成新结果。
那考虑有没有一种方法，可以未卜先知，在\(x\)插入某段子序列后，能够预测对结果的影响呢？回答是没有。那我们只好暴力的求解它产生的后续所有结果的可能性，最后对所有可能性的取值求一个最小值，也就是采用暴力搜索。

算法

既然采用暴搜，那么对时间复杂度简单分析，可以得到时间复杂度为\(O(n2^n)\)，需要对其进行剪枝处理。本题可以借鉴于母题LISⅡ的贪心性质进行优化。

优化

可以用两个数组，分别存储每个上升子序列的末尾数，每个非上升子序列的末尾数值，以便快速定位我们需要插入到哪个子序列后面，并且这种贪心思路得到的两个数组一定是具有单调性的，找到的第一个符合条件的数即可退出循环，也可以采用二分优化进一步优化。

如何搜索

由于本题n的范围较小，可以使用迭代加深搜索求解答案，也可以记录一个全局最小值，不断进行更新。

Code

此处直接贴yls代码。

int n;
int h[N];
int up[N], down[N];

bool dfs(int depth, int u, int su, int sd)
{
    // 如果上升序列个数 + 下降序列个数 > 总个数是上限，则回溯
    if (su + sd > depth) return false;
    if (u == n) return true;

    // 枚举放到上升子序列中的情况
    bool flag = false;
    for (int i = 1; i <= su; i ++ )
        if (up[i] < h[u])
        {
            int t = up[i];
            up[i] = h[u];
            if (dfs(depth, u + 1, su, sd)) return true;
            up[i] = t;
            flag = true;
            break;  
        }
    if (!flag) 
    {
        up[su + 1] = h[u];
        if (dfs(depth, u + 1, su + 1, sd)) return true;
    }

    // 枚举放到下降子序列中的情况
    flag = false;
    for (int i = 1; i <= sd; i ++ )
        if (down[i] > h[u])
        {
            int t = down[i];
            down[i] = h[u];
            if (dfs(depth, u + 1, su, sd)) return true;
            down[i] = t;
            flag = true;
            break;
        }
    if (!flag) 
    {
        down[sd + 1] = h[u];
        if (dfs(depth, u + 1, su, sd + 1)) return true;
    }

    return false;
}

int main()
{
    while (cin >> n, n)
    {
        for (int i = 0; i < n; i ++ ) cin >> h[i];

        int depth = 0;
        while (!dfs(depth, 0, 0, 0)) depth ++ ;     // 迭代加深搜索

        cout << depth << endl;
    }

    return 0;
}

最长公共上升子序列

状态表示f[i][j]

  • 集合
    所有在\(A[1-i]\)中和\(B[1-j]\)中出现过，并且以\(B[j]\)结尾的公共上升子序列的集合
  • 属性
    max

状态计算

  • \(A[i]\)不包含在公共子序列中

    \[f[i][j] = f[i-1][j] \]

  • \(A[i]\)包含在公共子序列中
    首先一定存在\(A[i]=B[j]\)，因为\(A[i]\)如若包含，一定是在最后一个。
    其次根据倒数第二个数对集合再划分成\(1- (i-1)\)段，进行求解，可得转移方程为

\[f[i][j] = Max(f[i-1][k]),k \in {1,2,3,4...j-1} \]

Code

直接上yls代码。

for (int i = 1; i <= n; i ++ )
    {
        int maxv = 1;
        for (int j = 1; j <= n; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
            if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
动态规划学习

相关

标签