【C++】洛谷B3637 最长上升子序列

这篇具有很好参考价值的文章主要介绍了【C++】洛谷B3637 最长上升子序列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

最长上升子序列

题目描述

这是一个简单的动规板子题。

给出一个由 n ( n ≤ 5000 ) n(n\le 5000) n(n5000) 个不超过 1 0 6 10^6 106 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

最长上升子序列是指,从原序列中按顺序取出一些数字排在一起,这些数字是逐渐增大的。

输入格式

第一行,一个整数 n n n,表示序列长度。

第二行有 n n n 个整数,表示这个序列。

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

6
1 2 4 1 3 4

样例输出 #1

4

提示

分别取出 1 1 1 2 2 2 3 3 3 4 4 4 即可。

思路: 用dp[i]表示序列中第i个元素处的最长上升子序列,那么如果想知道dp[i]的值,则需要找到第i个元素之前的最长上升子序列且此子序列的最大元素不能比当前元素大。如果第i个元素前所有的子序列中元素都比它自身大,则说明此时的元素不能与之前的元素构成上升子序列,那么此时dp[i]的值就为1

代码:文章来源地址https://www.toymoban.com/news/detail-825643.html

#include <bits/stdc++.h>
using namespace std;
int a[5000], ans[5000], n;
int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    ans[0] = 1;
    for(int i = 1; i < n; i++){
        int maxx = 0;
        for(int j = 0; j < i; j++){
            if(a[j] < a[i]) maxx = max(maxx, ans[j]);
        }
        ans[i] = maxx + 1;
    }
    sort(ans, ans + n);
    cout << ans[n - 1];
    return 0;
}

到了这里,关于【C++】洛谷B3637 最长上升子序列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划—— 最长上升子序列模型 解题记录

    一些想法:         现在是2024-3-15 06:01:22 哈哈卷死我可爱的舍友们~ 这两天又想起来开学的时候立下的刷完kuangbin专题的flag(快进到干不完) 总是先把Acwing的提高课看完吧 每天这样干一点总能干完的hhhhh,这会在喝npy买的奶茶,超多椰果真的好喝爱了爱了。 解题报告:

    2024年04月13日
    浏览(42)
  • AcWing 1.2.1 最长上升子序列模型 + 动态规划 + 图解(详细)

    (1)acwing 4557. 最长上升子序列  4557. 最长上升子序列 - AcWing题库 给定一个长度为 N 的整数序列  a1,a2,…,aN 。请你计算该序列的 最长上升子序列的长度 。上升子序列是指数值 严格单调递增的子序列 输入格式 第一行包含整数 N 第二行包含 N个整数 a1,a2,…,aN 输出格式 一行

    2024年02月06日
    浏览(38)
  • 动态规划系列 | 最长上升子序列模型(下)| 拦截导弹一网打尽!

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

    2024年02月03日
    浏览(49)
  • 洛谷 P2782 友好城市 线性DP 最长上升子序列 二分查找 lower_bound

    🍑 算法题解专栏 有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸,而且不同城市的友好城市不相同。每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市,但是由于河上雾太大,政

    2024年02月02日
    浏览(62)
  • 最长上升子序列问题(LIS问题)与最长不上升子序列问题的四种方法(c++ 模板代码)

    最大上升子序列问题也叫做LIS问题,与最大公共子序列LCS问题是一类经典问题,在本章我们将总结一下求解 LIS最大上升子序列 的 几种方法 ,同时也会给出对应的 最大不上升子序列的求解方法。 关于LCS问题,我在后面会再出一篇博客来讲解, 废话不多说,我们直接进入正题

    2024年02月03日
    浏览(43)
  • LeetCode | C++ 动态规划——300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

    300题目链接 dp 数组定义 dp[i] 表示 i 之前包括 i 的以 nums[i]结尾 的最长递增子序列的长度 需要包含nums[i]结尾,不然在做递增比较的时候,就没有意义了。 递推公式 位置 i 的最长递增子序列 等于 j 从 0 到 i - 1各个位置的最长递增子序列 + 1 的 最大值 if (nums[i] nums[j]) dp[i] = ma

    2024年02月16日
    浏览(45)
  • C++ 求解最长公共子序列(不仅仅求出其大小)(简单易懂!!!)(动态规划)

    求解两个数组的最长公共子序列我们需要用到的知识点有:动态规划dp,递归算法 先来说说动态规划dp 很多初学者在学习动态规划的时候总是百思不得其解,什么是动态规划呢,其实总结来说就是程序将计算过的结果记录下来,在下次使用到这条记录的时候不需要再次计算,

    2024年02月04日
    浏览(43)
  • C++ 动态规划经典案例解析之最长公共子序列(LCS)_窥探递归和动态规划的一致性

    动态规划处理字符相关案例中,求 最长公共子序列 以及求 最短编辑距离 ,算是经典中的经典案例。 讲解此类问题的算法在网上一抓应用一大把,即便如此,还是忍不住有写此文的想法。毕竟理解、看懂都不算是真正掌握,唯有瞧出其中玄机,能有自己独有的见解和不一样

    2024年02月13日
    浏览(37)
  • 上升子序列的最大长度,递归-记忆化搜索-动态规划三步走

    题目描述: 小明有一个数组,他想从数组任意元素开始向后遍历,找出所有上升子序列,并计算出最长的上升子序列的长度。 数据范围: 每组数据长度满足 1≤n≤200 1≤n≤200 , 数据大小满足 1≤val≤350 1≤val≤350 输入描述: 数据共2行,第1行先输入数组的个数,第2行再输

    2024年04月22日
    浏览(41)
  • 最长公共上升子序列(LCIS)

    目录 一、前言 二、最长公共上升子序列 1、问题描述 2、基本思路 (1)状态表示 (2)状态计算 三、题例 1、上链接 2、基本思路 3、代码 (1)python未优化版 (2)python优化版 对于学计算机的同学来说,学习算法是一件非常重要的事情,废话不多讲,我们来讲讲“最长公共上

    2023年04月09日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包