img

知识辨析：

（1）字符子串：指的是字符串中连续的n个字符，如abcdefg中，ab，cde，fg等都属于它的字串。

（2）字符子序列：指的是字符串中不一定连续但先后顺序一致的n个字符，即可以去掉字符串中的部分字符，但不可改变其前后顺序。如abcdefg中，acdg，bdf属于它的子序列，而bac，dbfg则不是，因为它们与字符串的字符顺序不一致。

  1. 公共子序列：如果序列C既是序列A的子序列，同时也是序列B的子序列，则称它为序列A和序列B的公共子序列。如对序列 1,3,5,4,2,6,8,7和序列 1,4,8,6,7,5 来说，序列1,8,7是它们的一个公共子序列。

最长上升子序列（Longest Increasing Subsequence，LIS）

我们要求序列中最长的单调增的子序列（不一定连续）的长度,也有些情况求的是最长非降序子序列，二者区别就是序列中是否可以有相等的数。

关于这个问题我们很容易想到朴素的 O(\(n^2\)) 做法

朴素：

状态设计：F [ i ] 代表以 A [ i ] 结尾的 LIS 的长度

状态转移：F [ i ] = max { F [ j ] + 1 ，F [ i ] } (1 <= j < i，A[ j ] < A[ i ])

边界处理：F [ i ] = 1 (1 <= i <= n)

时间复杂度：O (n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
const int maxn = 103, INF = 0x7f7f7f7f;
int a[maxn], f[maxn];
int n,ans = -INF;
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++) 
    {
        cin>>a[i];
        f[i] = 1;
    }
    for(int i=1; i<=n; i++)
        for(int j=1; j<i; j++)
            if(a[j] < a[i])
                f[i] = max(f[i], f[j]+1);
    for(int i=1; i<=n; i++) 
        ans = max(ans, f[i]);
    cout<<ans;
    return 0;
}

贪心+二分：

对于一个上升子序列，显然其结尾元素越小，越有利于在后面接其他的元素，也就越可能变得更长。

换种表达方式dp[i]表示长度为i的上升子序列的最后一个元素的最小值。

现在我们有一个新元素a，对比dp的最后一个元素。如果a > dp[len] ，那么可以直接把a“接到”dp[len]的后面， 形成更长的上升子序列。即：dp[++len] = a;

否则，找到dp中第一个大于等于a的元素，用a替换它 。这样替换后既保证仍形成上升子序列，又使得该上升子序列的最后元素更小。

例子如下：

现在有序列4，8，9，5，6，7，2，7求LIS。

一个一个元素来看，首先无疑dp[1]=4 ，然后考察8，8>4，故把8加入尾部。然后9>8，也进入尾部，这时dp数组是{4, 8, 9}。

下一个元素是5，5<9，不能塞入尾部。我们找到第一个大于等于5的元素，是8。4->8是长度为2的上升子序列，4->5也是，但是5比8更小，所以更有潜力更新后面的子序列。所以把8换成5，现在dp是{4, 5, 9}。同样的道理dp又变成{4, 5, 6}。

现在我们尝到甜头了，因为下一个元素是7，本来是没有机会进入序列的，现在却可以了。于是dp变成{4, 5, 6, 7}。注意，显然dp是递增的（两种转移都不会破坏递增性），但这并不意味着它就是所求的上升子序列，你看，下一个元素是2，它会把dp更新成{2, 5, 6, 7}，但原序列并没有一个子序列是{2, 5, 6, 7}。

最后剩一个元素7，由于我们在求严格上升的子序列，不能将它插入尾部，于是我们把7替换成7——这个元素对子序列长度没有贡献。好了，最后得到的数组长度是4，所以最长上升子序列的长度就是4 。

由于dp数组是递增的，因此可以进行二分查找。

1
2
3
4
5
6
7
8
int len = 0;
for (int i = 0; i < n; ++i)
{
    if (dp[len] < A[i])
        dp[++len] = A[i];
    else
        *lower_bound(dp + 1, dp + len + 1, A[i]) = A[i];
}

[NOIP1999 提高组] 导弹拦截

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行，若干个整数，中间由空格隔开。

输出格式

两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

样例 #1

样例输入 #1

1
389 207 155 300 299 170 158 65

样例输出 #1

1
2
6
2

提示

对于前 \(50\%\) 数据（NOIP 原题数据），满足导弹的个数不超过 \(10^4\) 个。该部分数据总分共 \(100\) 分。可使用\(\mathcal O(n^2)\) 做法通过。
对于后 \(50\%\) 的数据，满足导弹的个数不超过 \(10^5\) 个。该部分数据总分也为 \(100\) 分。请使用 \(\mathcal O(n\log n)\) 做法通过。

对于全部数据，满足导弹的高度为正整数，且不超过 \(5\times 10^4\)。

此外本题开启 spj，每点两问，按问给分。

NOIP1999 提高组 第一题

\(\text{upd 2022.8.24}\)：新增加一组 Hack 数据。

第一问显然就是求解最长不上升子序列

第二问要求能分成多少个，根据Dilworth定理

对于一个偏序集，最少链划分等于最长反链长度。

因此药求解最长上升子序列的长度，因此最后代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;
int A[100005], dp[100005];
int main()
{
    int n = 0, len = 0;
    while (cin >> A[n])
        n++;
    memset(dp, 127, sizeof(dp)); // 其实这里只需要初始化dp[0]为INF即可
    for (int i = 0; i < n; ++i)
    {
        if (dp[len] >= A[i])
            dp[++len] = A[i];
        else
            *upper_bound(dp + 1, dp + len + 1, A[i], greater<int>()) = A[i];
    }
    cout << len << endl;
    len = 0;
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; ++i)
    {
        if (dp[len] < A[i])
            dp[++len] = A[i];
        else
            *lower_bound(dp + 1, dp + len + 1, A[i]) = A[i];
    }
    cout << len << endl;
    return 0;
}

最长公共子序列((Longest Common Subsequence))

英文缩写为LCS。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。而最长公共子串(要求连续)和最长公共子序列是不同的.

最长公共子序列（LCS）也不一定唯一

，对于固定的两个数组，虽然最LCS不一定唯一，但LCS的长度是一定的。

采取递推的方式：

1
2
3
4
5
6
7
8
9
10
11
12
while (cin >> s1 >> s2)
{
    memset(dp, 0, sizeof(dp));
    int n1 = strlen(s1), n2 = strlen(s2);
    for (int i = 1; i <= n1; ++i)
        for (int j = 1; j <= n2; ++j)
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    cout << dp[n1][n2] << endl;
}

最长公共子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
while (cin >> s1 >> s2)
{
    memset(dp, 0, sizeof(dp));
    int n1 = strlen(s1), n2 = strlen(s2), ma = 0;
    for (int i = 1; i <= n1; ++i)
        for (int j = 1; j <= n2; ++j)
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = 0;
    for (int i = 1; i <= n1; ++i)
        for (int j = 1; j <= n2; ++j)
            ma = max(ma, dp[i][j]);
    cout << ma << endl;
}