2、最长上升子序列模型(LIS: Longest Increasing Subsequence)

895. 最长上升子序列

题目链接

题目给的数据范围是1000,所以我们可以用 dp 来做,通过闫氏dp分析法 从集合角度分析,如下image-20220912171814041

根据上面dp分析,实现代码如下

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

const int N = 1010;
int f[N], a[N], n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++ i)
        cin >> a[i];
    
    for (int i = 1; i <= n; ++ i) {
        // 不能接前面任何上升子序列后面
        f[i] = 1;
        // 接在前面上升子序列后面
        for (int j = i - 1; j > 0; -- j) 
            if (a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);
    }
    
    // 上面循环结束,f[i] 就表示以 a[i] 结尾上升子序列的最大长度, 接下来在这个集合中取最值即可
    int res = 0;
    for (int i = 1; i <= n; ++ i)
        res = max(res, f[i]);
    
    cout << res << endl;
    return 0;
}

896. 最长上升子序列 II

题目链接

此题是上一题的扩展,相比于上一题,数据范围增大到 100000,所以,我们不能简单的使用dp去做。这个题我们可以通过 贪心来分析。

  • 我们求出相同长度子序列中,结尾元素最小的那个,子序列。
  • 将该子序列的最后一个元素,维护在指定的列表中。
  • 根据上诉规则,我们能够知道该列表必然是 单调递增的。
  • 证明:假设长度 为 5 的子序列的结尾元素 a,和长度为 6的子序列的 第5个元素 b。假设存在 b < a,那么 跟上面规则就存在矛盾了(因为我们保存的是,指定长度子序列结尾元素最小的)。
  • 所以我们可以通过,在该列表中找到最大且小于当前元素的值,并将当前值接在它后面,更新长度。

实现代码如下:

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

const int N = 1e5 + 10;
int a[N], q[N], n;

int main() {
    cin >> n;
    for (int i = 0; i < n; ++ i)
        cin >> a[i];
    
    int len = 0;
    // 处理边界,保证长度为1的子序列能够找到小于它的数
    q[0] = -2e9;
    
    for (int i = 0; i < n; ++ i) {
        int l = 0, r = len;
        // 二分找到,小于当前数最大的那个
        while (l < r) {
            int mid = l + r + 1 >> 1;
            // q[mid] < a[i] 说明,我们要找的数在 mid 和 mid 右边
            if (q[mid] < a[i])
                l = mid;
            else
                r = mid - 1;
        }
        
        // 更新最大长度
        len = max(len, r + 1);
        // 将当前点拼接
        q[r + 1] = a[i];
    }
    
    cout << len << endl;
    return 0;
}

1017. 怪盗基德的滑翔翼

题目链接

根据题目分析,基德可以从某一栋楼选则从左或从右进行滑行,因为求得是最远滑行距离(经过最多的房顶),所以

  • 我们设当前怪盗基德 在 k 栋楼。
  • 求出 1~k 范围内得最长上升子序
  • k ~ n 范围内最长下降子序列(转化成 n -> k 最长上身子序列)
  • 最后,把上面求出得值取 max,就是答案
  • 这里 的 k 取值为 1 ~ n

根据上面分析,代码实现如下:

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

const int N = 110;
int f[N], g[N], a[N];
int k, n;

int main() {
    cin >> k;
    while(k --) {
        cin >> n;
        for (int i = 1; i <= n; ++ i)
            cin >> a[i];
        
        
        // 1->n 方向上每个点的最长上升子序列
        for (int i = 1; i <= n; ++ i) {
            f[i] = 1;
            for (int j = i - 1; j > 0; -- j)
                if (a[i] > a[j])
                    f[i] = max(f[i], f[j] + 1);
        }
        
        
        // n->1 方向上每个点的最长上升子序列
        for (int i = n; i > 0; -- i) {
            g[i] = 1;
            for (int j = i + 1; j <= n; ++ j)
                if (a[i] > a[j])
                    g[i] = max(g[i], g[j] + 1);
        }
        
        // 枚举每个 k 
        int res = 0;
        for (int k = 1; k <= n; ++ k) 
            res = max(res, max(f[k], g[k]));
        
        cout << res << endl;
        
    }
    
    return 0;
}

1014. 登山

题目链接

分析题目,并提前相关条件

  • 每次浏览的经典的编号都要大于前一个浏览景点的编号。

  • 一旦开始下山,就不向上走了。且不连续浏览海拔相同的两个景点(也就是说,先严格递增在严格递减)

  • 所以我们下降的点为 k

  • 求出 1~k 最长上升子序列,k ~ n 求最长下降子序列(n -> k 最长上升子序列)

  • k 属于 1 ~ n

  • 最后的结果 为 max(f(k) + g(k) - 1) , f(k) 为以 a(k) 结尾的正向的最长上升子序列,g(k) 为以 a(k) 结尾反向最长上升子序列

实现代码如下:

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

const int N = 1010;
int f[N], g[N], a[N], n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++ i)
        cin >> a[i];
    
    // 1 -> n
    for (int i = 1; i <= n; ++ i) {
        f[i] = 1;
        for (int j = i - 1; j > 0; -- j)
            if (a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);
    }
    
    // n -> 1
    for (int i = n; i > 0; -- i) {
        g[i] = 1;
        for (int j = i + 1; j <= n; ++ j)
            if (a[i] > a[j])
                g[i] = max(g[i], g[j] + 1);
    }
    
    
    int res = 0;
    for (int i = 1; i <= n; ++ i)
        res = max(res, f[i] + g[i] - 1);
    
    cout << res << endl;
    
    return 0;
}

482. 合唱队形

题目链接

这个题和上面登山的题差不多,我们需要找出 先上升在下降序列的最大值,然后减去这个序列的长度就是答案

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

const int N = 110;
int f[N], g[N], a[N], n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++ i)
        cin >> a[i];
    
    // 1 -> n
    for (int i = 1; i <= n; ++ i) {
        f[i] = 1;
        for (int j = i - 1; j > 0; -- j)
            if (a[i] > a[j])
                f[i] = max(f[i], f[j] + 1);
    }
    
    // n -> 1
    for (int i = n; i > 0; -- i) {
        g[i] = 1;
        for (int j = i + 1; j <= n; ++ j)
            if (a[i] > a[j])
                g[i] = max(g[i], g[j] + 1);
    }
    
    int num = 0;
    for (int i = 1; i <= n; ++ i)
        num = max(num, f[i] + g[i] - 1);
    
    cout << n - num << endl;
    
    return 0;
}

1012. 友好城市

题目链接

根据题目分析,我们以一边的顺序排序,另一边的城市,然后我们可以发现,所有的合法建桥方式必然对应着一个上升子序列。所以,答案就是最长上升子序列。如下图 image-20220912194338671

最长上升子序列就是答案。

通过上面分析,代码实现如下

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

typedef pair<int, int> PII;
const int N = 5e3 + 10;
PII a[N];
int f[N], n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        int x, y;
        cin >> x >> y;
        a[i] = {x, y};
    }
    
    sort(a + 1, a + 1 + n);
    
    
    // 求最长上升子序列
    for (int i = 1; i <= n; ++ i) {
        f[i] = 1;
        for (int j = i - 1; j > 0; -- j) 
            if (a[i].second > a[j].second)
                f[i] = max(f[i], f[j] + 1);
    }
    
    
    // 求出最大值
    int res = 0;
    for (int i = 1; i <= n; ++ i)
        res = max(res, f[i]);
    
    cout << res << endl;
    
    return 0;
}

1016. 最大上升子序列和

题目链接

题目分析,进入dp分析如下image-20220912201403509

实现代码如下

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

const int N = 1010;
int f[N], a[N], n;

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

1010. 拦截导弹

题目链接

针对第一问分析,可以得知,我们需要求出最长不上升子序列即可。

针对第二问分析,我们使用贪心,流程如下

  • 从前向后扫描每个数,对于每个数进行如下策略:
    • 情况1:如果现有的子序列的结尾都小于当前数,则创建新的子序列
    • 情况2:将当前数放到结尾大于等于它最小的子序列后面
  • 证明贪心策略正确性,通过证明相等
    • 设 A 是贪心法得到的子序列个数,B 是最优解子序列个数
    • 只要我们能够证明 A >= B 且 B >= A, 得出 A = B, 就能说明 贪心策略是正确的。
    • 证明:B <= A
      • 因为 B 是最优解,必然存在 B <= A
    • 证明:A >= B
      • 我们首先找贪心法和最优放法,第一个放置位置不相同的值。证明如下图image-20220913120407991
  • 最后维护的数组的值是递增的。

根据上面分析,代码实现如下

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

const int N = 1010;
int height[N], f[N], squence[N] , n;

int main() {
    while(cin >> height[n]) n++;
    
    // 求不上升子序列
    for (int i = 0; i < n; ++ i) {
        f[i] = 1;
        for (int j = i - 1; j >= 0; -- j)
            if (height[i] <= height[j])
                f[i] = max(f[i], f[j] + 1);
    }
    
    // 求出最大值
    int maxMissile = 0;
    
    for (int i = 0; i < n; ++ i)
        maxMissile = max(maxMissile, f[i]);
    
    // 求出拦截所有导弹最少需要创建的子序列个数
    
    int cnt = 0;
    for (int i = 0; i < n; ++ i) {
        int l = 0, r = cnt;
        
        while (l < r) {
            int mid = l + r + 1 >> 1;
            // 找到最大小于当前这个数的值
            if (squence[mid] >= height[i])
                r = mid - 1;
            else
                l = mid;
        }
        
        // 判断找到的值,后一个元素是否大于当前导弹的高度,不大于开个新的子序列
        if (squence[r + 1] < height[i])
            squence[++ cnt] = height[i];
        else
            // 大于直接更新
            squence[r + 1] = height[i];
        
        
    }
    
    cout << maxMissile << endl;
    cout << cnt << endl;
    
    
    return 0;
}

187. 导弹防御系统

题目链接

这个题是上一个题第二问的扩展,该题有两种决策

  • 决策一:
    • 情况1:如果现有的子序列的结尾都小于当前数,则创建新的子序列
    • 情况2:将当前数放到结尾大于等于它的最小的子序列后面
  • 决策二:
    • 情况1:如果吸纳有子序列结尾都大于当前数,则创建新的子序列
    • 情况2:将当前数放到小于等于它最大的子序列后面
  • 通过上面两种决策,我们需要分别计算将当前数放到 上升子序列中和下降子序列中,并求出最优解。所以得加上 DFS 搜索

实现代码如下

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

const int N = 55;
int up[N], down[N], height[N], n; // up 表示所有严格上升子序列的结尾,其内部值是非严格单调下降, down 是表示所有严格下贱子序列结尾,其内布置是非严格单调上升的。
int ans;

void dfs(int u, int su, int sd) {
    if (su + sd >= ans) 
        return;
    
    if (u == n) {
        ans = su + sd;
        return;
    }
    
    // 枚举将当前数放到上升导弹序列里面
    int k = 0;
    while (k < su && up[k] >= height[u]) k ++;
    int t = up[k];
    up[k] = height[u];
    if (k < su) dfs(u + 1, su, sd);
    else dfs(u + 1, su + 1, sd);
    up[k] = t;
    
    // 枚举将当前数放到下降升导弹序列里面
    k = 0;
    while (k < sd && down[k] <= height[u]) k ++;
    t = down[k];
    down[k] = height[u];
    if (k < sd) dfs(u + 1, su, sd);
    else dfs(u + 1, su, sd + 1);
    down[k] = t;
}

int main() {
    while (cin >> n, n) {
        for (int i = 0; i < n; ++ i)
            cin >> height[i];
        
        ans = n;
        dfs(0, 0, 0);
        
        cout << ans << endl;
        
    }
    
    return 0;
}

272. 最长公共上升子序列

题目链接

这个题是最长上升子序列和公共子序列结合版,dp分析如下 image-20220913124426875

根据上面分析,代码实现如下

暴力版实现: O(n^3)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3010;
int a[N], b[N], f[N][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) {
            // 不包含a[i] 的情况
            f[i][j] = f[i - 1][j];
            
            // 包含a[i] 的情况
            if (a[i] == b[j]) {
                f[i][j] = max(f[i][j], 1); // 初始值
                for (int k = j - 1; k > 0; -- k)
                    if (b[k] < a[i])
                        f[i][j] = max(f[i][j], f[i - 1][k] + 1);
            }
        }
        
    int res = 0;
    for (int i = 1; i <= n; ++ i)
        res = max(res, f[n][i]);
        
    cout << res << endl;
    
    return 0;
}

优化复杂度:O(n^2)

因为我们可以发现上面,b[k] < a[i] 和当前的 j 没有关系,且这层循环求的是 f(i -1 , k) + 1在 k < j 范围内的最大值。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3010;
int a[N], b[N], f[N][N], g[N][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) {
        g[i][0] = 1;
        for (int j = 1; j <= n; ++ j) {
            // 不包含a[i] 的情况
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j]) f[i][j] = max(f[i][j], g[i][j - 1]);
            g[i][j] = g[i][j - 1];
            if (b[j] < a[i]) g[i][j] = max(g[i][j], f[i][j] + 1);
        }
    }    
    int res = 0;
    for (int i = 1; i <= n; ++ i)
        res = max(res, f[n][i]);
        
    cout << res << endl;
    
    return 0;
}

优化空间:O(n^2)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 3010;
int a[N], b[N], f[N][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) {
        int maxv = 1;
        for (int j = 1; j <= n; ++ j) {
            // 不包含a[i] 的情况
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
            if (b[j] < a[i]) maxv = max(maxv, f[i][j] + 1);
        }
    }    
    int res = 0;
    for (int i = 1; i <= n; ++ i)
        res = max(res, f[n][i]);
        
    cout << res << endl;
    
    return 0;
}