动态规划刷题(算法竞赛、蓝桥杯)--合唱队形(线性DP)

1、题目链接:[NOIP2004 提高组] 合唱队形 - 洛谷

477e24dca970422f8f847e9feab4a003.png

#include <bits/stdc++.h>
using namespace std;
int n,ans;
int a[105],f[105][2];//f[i][2]中2表示正反两个方向int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}//正方向求最长上升子序列 a[0]=0;//初始化下标0 for(int i=1;i<=n;i++){for(int j=0;j<i;j++){if(a[i]>a[j]){f[i][0]=max(f[i][0],f[j][0]+1);}}}//反方向求最长上升子序列 a[n+1]=0;//初始化下标n+1 for(int i=n;i;i--){for(int j=n+1;j>i;j--){if(a[i]>a[j]){f[i][1]=max(f[i][1],f[j][1]+1);}}}for(int i=1;i<=n;i++){ans=max(f[i][0]+f[i][1]-1,ans);//正向加反向减去重叠的1个 }printf("%d\n",n-ans);//总数减去合法序列即为出队人数 return 0;
}

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/296169.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

总结UDP协议各类知识点

前言 本篇博客博主将详细地介绍UDP有关知识点&#xff0c;坐好板凳发车啦~ 一.UDP特点 1.无连接 UDP传输的过程类似于发短信&#xff0c;知道对端的IP和端口号就直接进行传输&#xff0c;不需要建立连接&#xff1b; 2.不可靠传输 没有任何的安全机制&#xff0c;发送端发…

C语言:文件操作(一)

目录 前言 1、为什么使用文件 2、什么是文件 2.1 程序文件 2.2 数据文件 2.3 文件名 3、文件的打开和关闭 3.1 文件指针 3.2 文件的打开和关闭 结&#xff08;一&#xff09; 前言 本篇文章将介绍C语言的文件操作&#xff0c;在后面的内容讲到&#xff1a;为什么使用文…

大数据设计为何要分层,行业常规设计会有几层数据

大数据设计通常采用分层结构的原因是为了提高数据管理的效率、降低系统复杂度、增强数据质量和可维护性。这种分层结构能够将数据按照不同的处理和应用需求进行分类和管理&#xff0c;从而更好地满足不同层次的数据处理和分析需求。行业常规设计中&#xff0c;数据通常按照以下…

C++11:声明 初始化

C11&#xff1a;声明 & 初始化 初始化{ }初始化initializer_list 声明autodecltypenullptr 初始化 { }初始化 在C98中&#xff0c;允许使用花括号{ }对数组或者结构体元素进行统一的列表初始化。 用{ }初始化数组&#xff1a; int arr[] { 1, 2, 3, 4, 5 };用{ }初始化…

Qt C++ | Qt 元对象系统、信号和槽及事件(第一集)

01 元对象系统 一、元对象系统基本概念 1、Qt 的元对象系统提供的功能有:对象间通信的信号和槽机制、运行时类型信息和动态属性系统等。 2、元对象系统是 Qt 对原有的 C++进行的一些扩展,主要是为实现信号和槽机制而引入的, 信号和槽机制是 Qt 的核心特征。 3、要使用元…

VMware虚拟机三种网络模式配置

vmware有三种网络工作模式&#xff1a;Bridged&#xff08;桥接模式&#xff09;、NAT&#xff08;网络地址转换模式&#xff09;、Host-Only&#xff08;仅主机模式&#xff09;。 1. 打开网络编辑器&#xff08;编辑 --> 虚拟网络编辑器&#xff09; 在主机上有VMware Ne…

【阿里淘天笔试题汇总】2024-04-03-阿里淘天春招笔试题(第一套)-三语言题解(CPP/Python/Java)

&#x1f36d; 大家好这里是KK爱Coding &#xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新淘天近期的春秋招笔试题汇总&#xff5e; &#x1f4bb; ACM银牌&#x1f948;| 多次AK大厂笔试 &#xff5c; 编程一对一辅导 &#x1f44f; 感谢大家的订阅➕ 和 喜欢&#x1f…

[RK3588-Android12] 调试MIPI-双通道-压缩屏(Video Mode/MIPI Dphy 8Lane/DSC 144HZ)

问题描述 被测屏幕&#xff1a;小米Pad6 分辨率&#xff1a;1800X2880 模式&#xff1a;Video Mode/MIPI Dphy 8Lane/DSC 144HZ PPS: 11 00 00 89 30 80 0B 40 03 84 00 14 01 C2 01 C2 02 00 01 F4 00 20 01 AB 00 06 00 0D 05 7A 06 1A 18 00 10 F0 03 0C 20 00 06 0B 0B 33…

[Leetcode笔记] 动态规划相关

前言 写题目写到了一些和动态规划相关的内容&#xff0c;所以在这里记录一下 LCR 089 题解思路 总的来说&#xff0c;就是用一个数组去存储当前的最优解&#xff0c;然后从0开始一路向上顺推过去&#xff0c;求得最后一位的最优解。 class Solution { public:int rob(vect…

k8s calico由IPIP模式切换为BGP模式

按照官网calico.yaml部署后&#xff0c;默认是IPIP模式 查看route -n &#xff0c; 看到是tunl0口进行转发 怎么切换到BGP模式呢&#xff1f; kubectl edit ippool 将ipipMode由Always修改为Never &#xff0c;修改后保存文件即可。无需做任何操作&#xff0c;自动就切换为BG…

公众号爆文策略与实践:揭秘千万阅读量的秘密

1. 引言 介绍公众号爆文的重要性&#xff0c;以及分享个人通过每天投入半小时赚到30倍门票的经验。强调跟上大佬步伐&#xff0c;提升认知的重要性。 2. 爆文的底层逻辑 2.1 推荐的底层逻辑 内容分发机制的变化&#xff0c;从仅限于直接关注到通过搜索、浏览推荐等多种方式…

【详解】Windows系统安装Nginx及简单使用

【详解】Windows系统安装Nginx及简单使用 一、Nginx是什么&#xff1f; “Nginx 是一款轻量级的 HTTP 服务器&#xff0c;采用事件驱动的异步非阻塞处理方式框架&#xff0c;这让其具有极好的 IO 性能&#xff0c;时常用于服务端的反向代理和负载均衡。”Nginx 是一款 http 服…

实景三维:城市数据要素的新维度

引言 在数字化转型的大潮中&#xff0c;数据已成为推动社会发展的关键要素。实景三维技术&#xff0c;作为一种新兴的数据表达形式&#xff0c;正在成为城市数据要素中不可或缺的一部分。它不仅丰富了数据的类型&#xff0c;更为城市规划、管理和服务提供了全新的视角。本文将…

N1912A安捷伦N1912A功率计

181/2461/8938产品概述&#xff1a; 安捷伦N1912A双通道P系列宽带功率传感器为R&D和制造工程师提供精确和可重复的功率测量&#xff0c;应用市场包括航空航天和国防&#xff08;雷达&#xff09;、无线通信和无线802.11a/b/g网络。该仪表/传感器组合提供的测量包括峰值功率…

QT-自定义参数设计框架软件

QT-自定义参数设计框架软件 前言一、演示效果二、使用步骤1.应用进行参数注册2.数据库操作单例对象3.参数操作单例对象 三、下载链接 前言 常用本地数据参数通常使用的是xml等文本的格式&#xff0c;进行本地的数据参数的存储。这种参数的保存方式有个致命的一点&#xff0c;就…

基于单片机20v数字电压表仿真系统设计

**单片机设计介绍&#xff0c;基于单片机20v数字电压表仿真系统设计 文章目录 一 概要二、功能设计三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机20V数字电压表仿真系统设计的主要目标是实现一个能够准确测量和显示20V直流电压的仿真系统。以下是该设计的主…

Sy6 编辑器vi的应用(+shell脚本3例子)

实验环境&#xff1a; 宿主机为win11&#xff0c;网络&#xff1a;10.255.50.5 6389 WSL2 ubuntu 目标机的OS&#xff1a;Ubuntu 内核、版本如下&#xff1a; linuxpeggy0223:/$ uname -r 5.15.146.1-microsoft-standard-WSL2 linuxpeggy0223:/$ cat /proc/version Linux vers…

VMware创建Ubuntu虚拟机详细教程

下载ISO映像文件 进入官网下载&#xff1a;Download Ubuntu Desktop | Download | Ubuntu 下面是一些其他的下载路径&#xff1a; 中国官网 https://cn.ubuntu.com/ 中科大源 Index of /ubuntu-releases/ (ustc.edu.cn) 阿里云开源镜像站 ubuntu-releases安装包下载_开源镜像…

真·面试题总结——JVM虚拟机

JVM虚拟机 JVM虚拟机规范与实现 JVM虚拟机规范 JVM虚拟机实现 JVM的常见实现 JVM虚拟机物理架构 JVM虚拟机的运转流程 JVM类加载过程 JVM类加载器及类加载器类型 JVM类加载器双亲委派机制 JVM运行时数据区的内存模型 JVM运行时数据区的内存模型&#xff1a;程序计数器…

day08 java 静态方法调用 方法的内存实现机制

目录 静态方法调用 方法的内存实现 静态方法调用 静态方法&#xff1a; 静态方法要在方法上用修饰符static。 静态方法可以通过类名调用 &#xff1a;类名.方法名&#xff08;&#xff09;或者 直接调用 &#xff1a;方法名&#xff08;&#xff09; 在同一个类中时&#xf…