动态规划——最长上升子序列模型

🕗 发布于 2025-01-14 10:05 动态规划算法

题目清单

在这里插入图片描述

acwing895.最长上升子序列

给定一个长度为 $N$ 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式
第一行包含整数 $N$ 。

第二行包含 $N$ 个整数，表示完整序列。

输出格式
输出一个整数，表示最大长度。

数据范围
$1 \leq N \leq 1000$ ， $10^9≤$ 数列中的数 $10^9$

输入样例：

7
3 1 2 1 8 5 6

输出样例：

4

$d p [i]$ :以 $s [i]$ 结尾的所有上升子序列
$d p [i] = ma x (d p [i], d p [j] + 1) (j < i, s [j] < s [i])$

#include <iostream>
using namespace std;
#define N 1010
int dp[N],s[N];
int n;
int main()
{
    cin >> n;
    int maxn = 0;
    for (int i = 1; i <= n; i ++ ) cin >> s[i];
    for (int i = 1; i <= n; i ++ )
    {
        dp[i] = 1;
        for (int j = 1; j < i; j ++ )
        if (s[j] < s[i]) dp[i] = max(dp[i], dp[j] + 1);
        maxn = max(maxn, dp[i]);
    }
    cout << maxn << endl;
    return 0;
}

acwing1017.怪盗基德的滑翔翼

和LIS问题，基本相同，唯一的区别在一本问题可以向两个方向滑行，所以就相当于做两次dp，去两次中的最大值。

$d p [i]$ :以 $s [i]$ 结尾的所有上升子序列
正向时： $d p [i] = ma x (d p [i], d p [j] + 1) (j < i, s [j] < s [i])$
反向时： $d p [i] = ma x (d p [i], d p [j] + 1) (j > i, s [j] < s [i])$

#include <iostream>
using namespace std;
#define N 110
int dp[N], s[N];
int T, n;
int main()
{
    cin >> T;
    while (T -- )
    {
        cin >> n;
        int maxn = 0;
        for (int i = 1; i <= n; i ++ ) cin >> s[i];
        for (int i = 1; i <= n; i ++ )
        {
            dp[i] = 1;
            for (int j = 1; j < i; j ++ )
            {
                if(s[j] < s[i]) 
                dp[i] = max(dp[i], dp[j] + 1);
            }
            maxn = max(maxn, dp[i]);
        }
        for (int i = n; i >= 1; i -- )
        {
            dp[i] = 1;
            for (int j = n; j > i; j -- )
            {
                if(s[j] < s[i]) 
                dp[i] = max(dp[i], dp[j] + 1);
            }
            maxn = max(maxn, dp[i]);
        }
        cout << maxn << endl;
    }
    return 0;
}

acwing1014.登山

和1017比较相似，1017进行了正向反向两次dp，取两次中的d最大值，本问题相当于是求先上升后下降的最长子序列，需要进行正向反向两次dp，求完之后对应位置求和，最后再遍历一遍求最大值。

$d p 1 [i]$ :以 $s [i]$ 结尾的所有上升子序列
$d p 1 [i] = ma x (d p 1 [i], d p 1 [j] + 1) (j < i, s [j] < s [i])$

$d p 2 [i]$ :以 $s [i]$ 结尾的所有下降子序列
$d p 2 [i] = ma x (d p 2 [i], d p 2 [j] + 1) (j > i, s [j] < s [i])$

#include <iostream>
using namespace std;
#define N 1010
int dp1[N], dp2[N], s[N];
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> s[i];
    for (int i = 1; i <= n; i ++ )
    {
        dp1[i] = 1;
        for (int j = 1; j < i; j ++ )
        if(s[i] > s[j])
        dp1[i] = max(dp1[i], dp1[j] + 1);
    }
    for (int i = n; i >= 1; i -- )
    {
        dp2[i] = 1;
        for (int j = n; j > i; j -- )
        if (s[i] > s[j])
        dp2[i] = max(dp2[i], dp2[j] + 1);
    }
    int maxn = 0;
    for (int i = 1; i <= n; i ++ )
    {
         dp1[i] += (dp2[i] - 1);
         maxn = max(maxn, dp1[i]);
    }
   cout << maxn;
    return 0;
}

acwing482.合唱队形

和上一次完全相似，唯一的区别在于本问题问的是至少移去多少人，所以需要用n减去最长先上升后下降序列的长度。

#include <iostream>
using namespace std;
#define N 110
int dp1[N], dp2[N], s[N];
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> s[i];
    for (int i = 1; i <= n; i ++ )
    {
        dp1[i] = 1;
        for (int j = 1; j < i; j ++ )
        if(s[i] > s[j])
        dp1[i] = max(dp1[i], dp1[j] + 1);
    }
    for (int i = n; i >= 1; i -- )
    {
        dp2[i] = 1;
        for (int j = n; j > i; j -- )
        if (s[i] > s[j])
        dp2[i] = max(dp2[i], dp2[j] + 1);
    }
    int maxn = 0;
    for (int i = 1; i <= n; i ++ )
    {
         dp1[i] += (dp2[i] - 1);
         maxn = max(maxn, dp1[i]);
    }
   cout << n - maxn;
    return 0;
}

本问题和LIS问题唯一的区别在于一个求长度最长，一个让序列和最大，也正因此本问题只需要在LIS问题基础上做一些小修改。
$d p [i]$ :以 $s [i]$ 结尾的所有上升子序列
$d p [i] = ma x (d p [i], d p [j] + s [i]) (j < i, s [j] < s [i])$
LIS问题的状态转移方程为
$d p [i] = ma x (d p [i], d p [j] + 1) (j < i, s [j] < s [i])$ ,
本问题把1改成了s[i]，意味着不是长度加了1而是大小加了s[i]。

#include <iostream>
using namespace std;
#define N 1010
int dp[N], s[N];
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    cin >> s[i];
    int maxn = 0;
    for (int i = 1; i <= n; i ++ )
    {
        dp[i] = s[i];
        for (int j = 1; j < i; j ++ )
        if (s[i] > s[j]) 
        dp[i] = max(dp[i], dp[j] + s[i]);
        maxn = max(maxn, dp[i]);
    }
    cout << maxn;
}

acwing1012.友好城市

满足要求的组合一直是上坐标和下坐标的相对大小顺序是相同的，也正因此本问题等价于将每一对城市的组合按照上坐标的大小进行排序，再求下坐标的最长上升子序列长度。
在这里插入图片描述

$d p [i]$ :以 $s [i]$ 结尾的所有上升子序列
$d p [i] = ma x (d p [i], d p [j] + 1) (j < i, s [j] < s [i])$

#include <iostream>
#include <algorithm>
using namespace std;
#define N 5010
int dp[N];
pair<int, int> s[N];
int n;
int main()
{
    cin >> n;
    for (int i = 1; i <= n ;i ++ )
    cin >> s[i].first >> s[i].second;
    sort(s + 1, s + 1 + n);
    int maxn = 0;
    for (int i = 1; i <= n; i ++ )
    {
        dp[i] = 1;
        for (int j = 1; j < i; j ++ )
        if (s[i].second > s[j].second)
        dp[i] = max(dp[i], dp[j] + 1);
        maxn = max(maxn, dp[i]);
    }
    cout << maxn << endl;
    return 0;
}

acwing1010.拦截导弹

本题的第一部分就是一个LIS裸题。
第二部分要用贪心来解决，依次考虑每一个位置，对于每一个位置上的数可以把他放到当前已有的拦截系统，也可以单独开一个拦截系统。
易知如果能把他放在一个系统当中肯定优于单独开一个系统。证明：假设当前数是b，放在了a的后面，显然需要满足a>=b,此时所有拦截系统的最低高度分别是b，inf(还没有开出来的系统，用于和单独开一个系统做对照)，以及其他；如果单独开一个系统,此时所有拦截系统的最低高度分别是a，b，以及其他。两种情况做对比，都存在其他，可以消除；都存在b，可以消除；接下来只剩下inf以及a，很显然inf是更有的情况，所以把一个高度放在一个系统当中肯定优于单独开一个系统。
接下来考虑放到哪一个系统结果更优，显然要放在大于等于当前高度的最低高度后面结果更优。证明：假设当前数是c，系统中当前系统已拦截的导弹最低高度为a，b以及其他，满足关系a>=b>=c。假设放在了a后面，那么所有系统已拦截的导弹最低高度分别为c，b，以及其他；假设放在了b后面，那么所有系统已拦截的导弹最低高度分别为c，a，以及其他。两种情况做对比，都存在其他，可以消除；都存在c，可以消除；接下来只剩下b以及a，因为a>=b，所以第二种情况(放在b后面)能够为未来提供更好的选择方案。

#include <iostream>
using namespace std;
#define N 1010
int a[N];
int dp[N];
int g[N];
int n = 0;
int cnt = 0, maxn = 0;
int main()
{
    while(cin >> a[n + 1]) n ++ ;
    for (int i = 1; i <= n; i ++ ) 
    {
        dp[i] = 1;
        for (int j = 1; j < i; j ++ )
        {
            if (a[j] >= a[i]) 
            dp[i] = max(dp[i], dp[j] + 1);
        }
        maxn = max(maxn, dp[i]);
    }
    for (int i = 1; i <= n; i ++ ) 
    {
        int k = 1;
        while (g[k] < a[i] && k <= cnt) k ++ ;
        g[k] = a[i];
        if (k == cnt + 1) cnt ++ ; 
    }
    cout << maxn << endl << cnt << endl;
    return 0;
}

acwing187.导弹防御系统

和上一题相比，本题要求要么一直严格单调上升要么一直严格单调下降，不再是单一的下降，也正因此本题不能继续采用贪心的思想，需要使用搜索。

#include <iostream>
using namespace std;
#define N 60
int n, ans;
int a[N];
int up[N], down[N];
void dfs(int u, int su, int sd)
{
    if (su + sd >= ans) return ;
    if (u == n + 1)
    {
        ans = su + sd;
        return ;
    }
    int k = 0;
    while (up[k] <= a[u] && k < su) k ++ ;
    int t = up[k];
    up[k] = a[u];
    if(k == su) dfs(u + 1, su + 1, sd);
    else dfs(u + 1, su, sd);
    up[k] = t;
    k = 0;
    while(down[k] >= a[u] && k < sd) k ++ ;
    t = down[k];
    down[k] = a[u];
    if (k == sd) dfs(u + 1, su, sd + 1);
    else dfs(u + 1, su, sd);
    down[k] = t;
    return ;
}
int main()
{
    while (cin >> n, n)
    {
        ans = n;
        for (int i = 1; i <= n; i ++ ) cin >> a[i];
        dfs(1, 0, 0);
        cout << ans << endl;
    }
}

acwing272.最长公共上升子序列

本题结合了最长上升子序列以及最长公共子序列两道题的思想。
状态表示
集合： $d p [i] [j]$ :所有以第一个序列的前i个字母，第二个序列的前j个字母构成的，且以b[j]结尾的公共上升子序列。
属性： $ma x$
状态计算
在这里插入图片描述
分成两部分，第一部分为序列中不包含 $a [i]$ 的情况，第二部分是包含 $a [i]$ 的情况
$d p [i] [j] = ma x (d p [i - 1] [j], d p [i - 1] [k] + 1) (k < j 且 a [i] > b [k])$

#include <iostream>
using namespace std;
#define N 3010
int dp[N][N];
int a[N], b[N];
int 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 ++ )
        {
            dp[i][j] = dp[i - 1][j];
            if (a[i] == b[j]) dp[i][j] = max(dp[i][j], maxv);
            if (a[i] > b[j]) maxv = max(maxv, dp[i - 1][j] + 1);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i ++ ) res = max(res, dp[n][i]);
    cout << res;
    return 0;
}

原文地址：https://blog.csdn.net/m0_70897036/article/details/144629022

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：C#中的数据类型
下一篇：OpenCV基础：视频的采集、读取与录制

朝天椒USB服务器在万家基金的前置机应用案例
通过朝天椒USB服务器，万家基金可以将所有的Ukey统一连接到USB服务器上，并在服务端设置每个端口Ukey的类别、名称、授权用户、授权IP、连接密码等。在这样的背景下，万家基金选择了超融合虚拟化技术
阅读更多2025-01-15
Windows 11 开启 WSL（Windows Subsystem for Linux）完整指南
WSL（Windows Subsystem for Linux）可以让你在 Windows 上运行 Linux 的命令行工具和应用程序。以下是开启 WSL 的详细步骤。
阅读更多2025-01-15
微服务电商平台课程六：后端代码框架认识
本地环境搭建好，大家可以进行调试，并能够修改其中代码。后端技术栈Spring Boot是伴随着Spring4.0共同诞生的，它的目的就是简化spring的配置及开发，并协助开发人员可以整体管理应用程序
阅读更多2025-01-15
最好用的图文识别OCR -- PaddleOCR(4) 模型微调
PaddleOCR模型微调、模型测试、模型转换、推理模型应用
阅读更多2025-01-15
c语言 --- 字符串
创建方式存储位置是否可修改内容字符数组（如char str[]栈内存可以指向字符串常量的指针（如char *只读内存不可以（未定义行为）动态分配的字符串（如malloc堆内存可以逐个字符赋值的数组栈内
阅读更多2025-01-15
【C语言】【C++】报错：[错误]‘vector‘ does not name a type
需要使用标准命名空间。
阅读更多2025-01-15
深度学习中的卷积神经网络（CNN）：原理与应用详解
CNN的详解
阅读更多2025-01-15
艾体宝干货丨网络故障排除基本指南
本文提供了一份关于网络故障排除的全面指南，涵盖了故障排除的基本步骤和技巧，强调了获得全面可见性的重要性。通过详细的分析和实际案例，您将学习如何快速定位网络问题，优化网络性能，并提高整体系统的可靠性。无
阅读更多2025-01-15
Django基础之ORM初识
今天主要还是简单知识点，做个了解就行了，下次会和大家具体讲orm，那个篇幅就很长了，本章相当于是药引，下一期才是猛药。
阅读更多2025-01-15
抓包之tcpdump安装和使用
公司的运维同事，以及搞C，C++开发的同事，经常回通过tcpdump工具抓包来排查问题。可以看出该技能还是比较重要的，所以就想着也来学习下，并记录在这里，希望也能能够帮助到你，并用在实际工作中。
阅读更多2025-01-15

动态规划——最长上升子序列模型

题目清单

相关文章