动态规划--最长上升子序列模型(一)

简介: AcWing算法提高课内容,本文讲解 动态规划

文章目录

一、前言

二、AcWing 1017. 怪盗基德的滑翔翼

1.题目

2.逻辑解释

3.AC代码

三、AcWing 1014. 登山

1.题目

2.逻辑解释

3.AC代码

四、AcWing 482. 合唱队形

1.题目

2.逻辑解释

3.AC代码

五、AcWing 1012. 友好城市

1.题目

2.逻辑解释

3.AC代码

六、AcWing 1016. 最大上升子序列和

1.题目

2.逻辑解释

3.AC代码

七、AcWing 1010. 拦截导弹

1.题目

2.逻辑解释

3.AC代码

八、AcWing 187. 导弹防御系统

1.题目

2.逻辑解释

3.AC代码

九、AcWing 272. 最长公共上升子序列

1.题目

2.AC代码

十、额外的练习题


一、前言

AcWing算法提高课内容,本文讲解 动态规划


本篇包括以下题目:


⭐️AcWing 1017. 怪盗基德的滑翔翼

⭐️AcWing 1014. 登山

⭐️AcWing 1017. AcWing 1012. 友好城市

⭐️AcWing 1017. AcWing 1016. 最大上升子序列和

⭐️AcWing 1017. AcWing 1010. 拦截导弹

⭐️AcWing 1017. AcWing 187. 导弹防御系统

⭐️AcWing 1017. AcWing 272. 最长公共上升子序列

写博客有哪里不完善的地方或者有哪里表达错误希望大家提出来,博主会立即改正!望大家海涵

文末附有几道练习题目,读者在看懂上述题目之后可以拿来练手,题目链接为本人博客(博客中有原题链接),每道题目均附有题解。


本文需要先自修基础:线性DP


二、AcWing 1017. 怪盗基德的滑翔翼

1.题目

本题链接:怪盗基德的滑翔翼

本博客提供本题截图:

3.png

2.逻辑解释

我们把题目抽象一下,其实就是要求一个最长下降子序列,因为题目中说基德可以在任意一个房子的屋顶,所以我们只需要从左往右飞一遍,再从右往左飞一遍,两遍去最大值即可.

3.AC代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int h[N], f[N];
int main()
{
    int t;
    cin >> t;
    while (t -- )
    {
        int n;
        cin >> n;
        for (int i = 0; i < n; i ++ ) cin >> h[i];
        int res = 0;
        for (int i = 0; i < n; i ++ )    //n个房子依次遍历,往左飞
        {
            f[i] = 1;
            for (int j = 0; j < i; j ++ ) 
                if (h[j] < h[i])
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        for (int i = n - 1; ~i; i -- )   //n个房子依次遍历,往右飞
        {
            f[i] = 1;
            for (int j = n - 1; j > i; j -- ) 
                if (h[j] < h[i])
                    f[i] = max(f[i], f[j] + 1);
            res = max(res, f[i]);
        }
        cout << res << endl;
    }
    return 0;
}


三、AcWing 1014. 登山

1.题目

本题链接:登山

本博客提供本题截图:


image.png


2.逻辑解释

题目抽象后,本题其实就是求一个先上升再下降的序列的最大值,和上题思路其实一致,先做一次最长上升子序列f[i]再做一次最长下降子序列g[i],最后按照第 i个点分开求 max(f[i] + g[i] - 1)

3.AC代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int h[N], f[N], g[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> h[i];
    for (int i = 1; i <= n; i ++) 
    {
        f[i] = 1;
        for (int j = 1; j < i; j ++ ) 
            if (h[j] < h[i]) 
                f[i] = max(f[i], f[j] + 1);
    }
    for (int i = n; i; i -- )
    {
        g[i] = 1;
        for (int j = n; j > i; j -- ) 
            if (h[j] < h[i])
                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;
}



目录
相关文章
|
JavaScript 前端开发 开发工具
基于 Vue3.0 和 Ant Design Vue ,高颜值管理后台UI框架vue-vben-admin运行
基于 Vue3.0 和 Ant Design Vue ,高颜值管理后台UI框架vue-vben-admin运行
676 1
|
4月前
|
机器学习/深度学习 数据可视化 算法
数据分布不明确?5个方法识别数据分布,快速找到数据的真实规律
本文深入探讨了数据科学中分布识别的重要性及其实践方法。作为数据分析的基础环节,分布识别影响后续模型性能与分析可靠性。文章从直方图的可视化入手,介绍如何通过Python代码实现分布特征的初步观察,并系统化地讲解参数估计、统计检验及distfit库的应用。同时,针对离散数据、非参数方法和Bootstrap验证等专题展开讨论,强调业务逻辑与统计结果结合的重要性。最后指出,正确识别分布有助于异常检测、数据生成及预测分析等领域,为决策提供可靠依据。作者倡导在实践中平衡模型复杂度与实用性,重视对数据本质的理解。
334 3
数据分布不明确?5个方法识别数据分布,快速找到数据的真实规律
|
人工智能 自然语言处理
业界首家!阿里云智能媒体服务,卓越级通过中国信通院大模型媒体处理评估
阿里云智能媒体服务作为业界首家获得中国信通院“卓越级”通过。
业界首家!阿里云智能媒体服务,卓越级通过中国信通院大模型媒体处理评估
|
IDE Android开发 iOS开发
探索安卓与iOS系统的技术差异:开发者的视角
本文深入分析了安卓(Android)与苹果iOS两大移动操作系统在技术架构、开发环境、用户体验和市场策略方面的主要差异。通过对比这两种系统的不同特点,旨在为移动应用开发者提供有价值的见解,帮助他们在不同平台上做出更明智的开发决策。
|
11月前
|
SQL 监控 数据可视化
完全开源!国内首个完全开源JAVA企业级低代码平台
JeeLowCode 是一款专为企业打造的 Java 企业级低代码开发平台,通过五大核心引擎(SQL、功能、模板、图表、切面)和四大服务体系(开发、设计、图表、模版),简化开发流程,降低技术门槛,提高研发效率。平台支持多端适配、国际化、事件绑定与动态交互等功能,广泛适用于 OA、ERP、IoT 等多种管理信息系统,帮助企业加速数字化转型。
完全开源!国内首个完全开源JAVA企业级低代码平台
|
缓存 关系型数据库 MySQL
分享一个实用的MySQL一键巡检脚本
分享一个实用的MySQL一键巡检脚本
270 0
|
存储 API C++
【 QString接口大全】 Qt QString类使用示例
【 QString接口大全】 Qt QString类使用示例
504 1
|
存储 数据采集 Apache
众安保险 CDP 平台:借助阿里云数据库 SelectDB 版内核 Apache Doris 打破数据孤岛,人群圈选提速4倍
随着业务在金融、保险和商城领域的不断扩展,众安保险建设 CDP 平台以提供自动化营销数据支持。早期 CDP 平台依赖于 Spark + Impala + Hbase + Nebula 复杂的技术组合,这不仅导致数据分析形成数据孤岛,还带来高昂的管理及维护成本。为解决该问题,众安保险引入 Apache Doris,替换了早期复杂的技术组合,不仅降低了系统的复杂性,打破了数据孤岛,更提升了数据处理的效率。
1966 6
众安保险 CDP 平台:借助阿里云数据库 SelectDB 版内核 Apache Doris 打破数据孤岛,人群圈选提速4倍
|
人工智能 搜索推荐
AI助理小课堂02期
创建可分享的AI助理 助力个人和企业走进智能化生活和工作
|
前端开发 测试技术 开发者
深入理解 Webpack 热更新原理:提升开发效率的关键
深入理解 Webpack 热更新原理:提升开发效率的关键