最长上升子序列模型 2

• LCS: 最长公共子序列
• LIS: 最长上升子序列

1010 拦截导弹

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

某天，雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

动态规划

最长不上升子序列

贪心流程

从前往后扫描每个数，对于这个数：

1. 如果现有的所有子序列的结尾都小于当前数，则创建 新子序列
2. 反之，将当前数放进 结尾大于等于它 的 最小的 子序列后面

#include<bits/stdc++.h>

using namespace std;

const int N = 1010;
int n;
int a[N]; // 读的数字
int f[N]; // 动态规划
int g[N]; // 记录当前合法子序列的末尾min

int main()
{
    while (cin >> a[n]) n++; // a[0], a[1], ...

    // (1) 求正向: 最长不上升子序列
    int res = 0;
    for (int i=n-1; i>=0; i--) 
    {
        // 正向: 最长不上升子序列
        // 反向: 最长不下降子序列
        f[i] = 1;
        for (int j=n-1; j>i; j--)
        {
            if (a[i] >= a[j]) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
        res = max(res, f[i]);
    }

    cout << res << endl;

    // (2) 用 最少的 最长下降子序列 对原导弹数组进行全覆盖
    // 我们并不是真存了这么多子序列. 我们只用g[j]记录j号子序列的结尾导弹高度
    // - 如果i放不进来 就新建一个子序列. 放到g[j++]里面 作为新的j+1号子序列结尾
    // - 如果能放进来 就把子序列j号子序列结尾更新为i导弹的高度

    int cnt = 0; // 当前创建的 “正向: 最长不上升子序列” 总数
    for (int i=0; i<n; i++)
    {
        int k = 0; // 当前枚举到: 以k导弹结尾的子序列 每次循环前清空 保证从0号子序列的结尾开始搜

        while (k<cnt and g[k]<a[i]) k++;

        if (k >= cnt) {
            g[cnt++] = a[i]; // 如果都把当前序列数量搜完了还没有任何一个序列能放下i 我们就新开一个序列来存i
        }
        else {
            g[k] = a[i];
        }
    }

    cout << cnt << endl;

    return 0;
}

187 导弹防御系统

为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。

一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。

例如，一套系统先后拦截了高度为 3 和高度为 4 的两发导弹，那么接下来该系统就只能拦截高度大于 4 的导弹。

给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

dfs求全局最小

• 记一个全局最小值
• 迭代加深

#include<bits/stdc++.h>

using namespace std;

const int N = 100;

int n;
int a[N]; // 输入数组
int up[N], down[N]; // 最长上升 / 反向最长上升
int ans;

void dfs (int u, int su, int sd)
{
    // u: 第u个数
    // su: 所有 “最长上升子序列” 的总数
    // sd: 所有 “最长反向上升子序列” 的总数

    if (su + sd >= ans) return;
    if (u == n)
    {
        ans = su + sd;
        return;
    }

    // (1) 将当前数放入“最长上升子序列”
    int k = 0; // 考察的第k个“最长上升子序列”
    while (k<su and up[k] >= a[u]) k++;
    int tmp = up[k]; // dfs, 用来恢复现场

    up[k] = a[u]; // 加入
    if (k < su) dfs(u+1, su, sd); // 尾追加
    else dfs(u+1, su+1, sd); // 新开

    up[k] = tmp; // 恢复现场

    // (2) 将当前数放入“最长反向上升子序列”
    k = 0; // 考察的第k个“最长反向上升子序列”
    while (k < sd and down[k] <= a[u]) k++;
    tmp = down[k]; // dfs, 用来恢复现场

    down[k] = a[u]; // 加入
    if (k < sd) dfs(u+1, su, sd); // 尾追加
    else dfs(u+1, su, sd+1); // 新开

    down[k] = tmp; // 恢复现场
}

int main()
{
    while (cin >> n, n)
    {   // 多输入 (每次输入的测试数n不能为0)
        for (int i=0; i<n ;i++) cin >> a[i];

        ans = n;
        dfs(0, 0, 0);
        cout << ans << endl;
    }

    return 0;
}

特别注意一下上面: 求有多少个“最长上升子序列”个数的模板

897 最长公共子序列

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

const int maxn = 1e3 + 10;

string a, b;
int n, m;
int f[maxn][maxn];

int main()
{
    cin >> n >> m;
    string tmp_a, tmp_b;
    cin >> tmp_a >> tmp_b;
    a = " " + tmp_a;
    b = " " + tmp_b;

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

    cout << f[n][m] <<endl;
    return 0;
}

272 最长公共上升子序列

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。

小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。

小沐沐说，对于两个数列 A 和 B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。

奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。

不过，只要告诉奶牛它的长度就可以了

数列 A 和 B 的长度均不超过 3000

动态规划

• 状态表示: f[i, j]
  • 集合: 所有由 第一个序列的前i个字母，第二个序列的前j个字母，且 以b[j]结尾 的 公共上升子序列
    • 第一个序列的前i个字母，第二个序列的前j个字母 -> 最长公共子序列
    • 以b[j]结尾 -> 最长上升子序列 (写a[i]也可以, 对称)
  • 属性: Max / min / num
• 状态计算:
  • 

// 暴力版: f[][]
#include<bits/stdc++.h>

using namespace std;

const int N = 3010;

int n;
int a[N], b[N];
int f[N][N]; // 用于动态规划

int main()
{
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i];
    for (int i=1; i<=n; i++) cin >> b[i];

    for (int i=1; i<=n; i++)
    {
        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], 1);

                for (int k=1; k<j; k++)
                {
                    if (b[k] < b[j])
                        f[i][j] = max(f[i][j], f[i][k] + 1);
                }   
            }
        }
    }

    int res = 0;
    for (int j=1; j<=n; j++) res = max(res, f[n][j]);
    cout << res << endl;

    return 0;
}