当前位置: 首页 > news >正文

洛谷——P1091 合唱队形

【题目描述】

n 位同学站成一排,音乐老师要请其中的 n−k 位同学出列,使得剩下的 k 位同学排成合唱队形。

合唱队形是指这样的一种队形:设 kk 位同学从左到右依次编号为 1,2, … ,k,他们的身高分别为t_{1}​,t_{2}​, … ,t_{k}​,则他们的身高满足 t_{1}<……<t_{i}>……>t_{k} (1≤i≤k)。  

你的任务是,已知所有 n 位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。

【输入】

共二行。

第一行是一个整数 n(2≤n≤100),n 表示同学的总数。

第二行有 n 个整数,用空格分隔,第 i 个整数 ​t_{i}(130≤ t_{i}​ ≤230)是第 i 位同学的身高(厘米)。

【输出】

一个整数,最少需要几位同学出列。

样例输入

8
186 186 150 200 160 130 197 220

样例输出

4

解题思路

这个题目不是单纯的递增或者递减数列,而是先递增再递减。

我首先想的是:从1 到 n 存入身高,初始化动态 dp 数组,每个里面的值赋为 i-1(例如第 1 个 dp[1]=0),然后从 2 到 n 进行遍历(代表的是递增的节制点 k),然后分情况讨论:内部进行两个循环,一个循环对 1 至 k 进行考虑,如果不满足 a[j]<a[i],就重新赋值,dp[i]= min(dp[i],dp[j]+1),但是这里要考虑一个问题是:如果去掉了一个人(他的编号是 x),那么他的下一个人(x+1)的身高还是和第 x 个人比较,这里会有些复杂, dp 数组里面更新的最小值,是从哪一个人开始更新的,说明这个人不用考虑,可能还需要用一个值存储更新的这个人的前一个人的身高。这是计算递增情况的,然后递减情况类似。

然后我看了下题解,他们的思路都很像:是先用两层循环,目的是从第 1 个人到第 n 个人找对应下标的最大升序列,再用两层循环从第 n 个人到第 1 个人找对应下标的最大升序列。

题目不就是要找前一部分是升序,后一段是从后往前的升序嘛!那将两个升序对应的下标的值相加,注意要减一,因为前一段和后一段的中间那个数,计算了两次。

然后计算上的人数就是符合要求的,要求的是去除的人数,就用 n-max ,max是统计人数时出现的最大值。

先用代码解决找升序的问题:

for(i=1;i<=n;i++)//从左到右找递增的个数 {for(j=0;j<i;j++){if(a[j]<a[i])b[i]=max(b[i],b[j]+1);} }

不过要注意的是:尽管数列是从第 1 个人开始数的,但是内存循环的 j=0 ,全局变量中 a[0]=0,对于第一个人来说,这个人肯定要入列,这时 a[1]>a[0],b[1]=b[0]+1(其实也可以在初始化时就把b[1]  赋值为1,也是一样的效果)。 对于后一段也是同样的思路。

代码如下:

#include<stdio.h>
int a[105];
int b[105],c[105],sum;
int max(int x,int y)
{if(x<y)return y;elsereturn x;
}
int main()
{int n,i,j;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&a[i]);}for(i=1;i<=n;i++)//从左到右找递增的个数 {for(j=0;j<i;j++){if(a[j]<a[i])b[i]=max(b[i],b[j]+1);} }for(i=n;i>0;i--)//从左往右找递减的个数 {for(j=n+1;j>i;j--){if(a[i]>a[j])c[i]=max(c[i],c[j]+1);}}for(i=1;i<=n;i++)sum=max(sum,c[i]+b[i]-1);//找中途出现的最大值 printf("%d",n-sum);return 0;
}

相关文章:

洛谷——P1091 合唱队形

【题目描述】 n 位同学站成一排&#xff0c;音乐老师要请其中的 n−k 位同学出列&#xff0c;使得剩下的 k 位同学排成合唱队形。 合唱队形是指这样的一种队形&#xff1a;设 kk 位同学从左到右依次编号为 1,2, … ,k&#xff0c;他们的身高分别为​,​, … ,​&#xff0c;则…...

使用logstash把mysql同步到es,Kibana可视化查看

1&#xff1a;首先需要电脑本地有es环境&#xff0c;并且要牢记版本后&#xff0c;后续安装的logstash和Kibana一定要版本对应 查看es版本&#xff1a;http://localhost:9200/ 2&#xff1a;安装对应版本的logstash&#xff1a;找到自己对应ES版本&#xff0c;然后解压 Logst…...

Vue3.0 setup的使用及作用

目录开篇&#xff1a;1.什么是setup2.setup怎么使用3.setup中包含的生命周期函数3.setup相关参数4.setup特性总结总结开篇&#xff1a; 从vue2升级 vue3&#xff0c;vue3是可以兼容vue2。所以v3可以采用v2的选项式api&#xff0c;但是v2不能使用v3的组合式api&#xff0c;由于…...

Ubuntu18.04安装Vertica

目录下载安装包安装(Ubuntu18.04)配置 I/O Scheduler配置 TZSupport Tools配置 swapinessDisk ReadaheadEnabling chrony or ntpd自启动项错误处理后重装下载安装包 官网11.0版本或者10.0(deb)安装包可私信提供百度网盘链接&#xff1b; 安装(Ubuntu18.04) testvertica:~$ s…...

2.计算机基础-计算机网络面试题—基础知识、容器、面向对象、并发编程

本文目录如下&#xff1a;计算机基础-计算机网络 面试题一、基础知识简述 TCP 和 UDP 的区别&#xff1f;http与https的区别?Session 和 Cookie 有什么区别&#xff1f;URL是什么&#xff1f;由哪些部分组成&#xff1f;OSI 的 五层模型 都有哪些&#xff1f;get 和 post 请求…...

解决Mac 安装应用提示:xx已损坏,无法打开。 您应该将它移到废纸篓问题

许多新手mac 用户安装应用得时候会出现 “已损坏&#xff0c;无法打开。您应该将它移到废纸娄” 导致无法正常安装&#xff0c;其实应用软件b并没有损坏&#xff0c;只是系统安全设置&#xff0c;我们改如何解决呢&#xff1f; 1、开启允许任何来源 苹果已经取消了允许“任何…...

xpath注入[NPUCTF2020]ezlogin

[NPUCTF2020]ezlogin 打开界面 如果发现自己输入的信息由这样构成&#xff0c;可以往xpath注入上靠一下。 不管输入什么&#xff0c;很容易发现登陆就超时了&#xff0c;说明这里token是不断刷新的。 这样构造也是一样的目的都是为了闭合后面的&#xff0c;为啥有两个or呢 us…...

【Python学习笔记】22.Python3 数据结构

前言 本章节我们主要结合前面所学的知识点来介绍Python数据结构。 列表 Python中列表是可变的&#xff0c;这是它区别于字符串和元组的最重要的特点&#xff0c;一句话概括即&#xff1a;列表可以修改&#xff0c;而字符串和元组不能。 以下是 Python 中列表的方法&#xf…...

一文搞懂 什么是CPU上下文?为什么要切换?如何减少切换?

最近经常有小伙伴问到的一些问题&#xff0c;比较集中的是关于CPU切换. 实际用C/C&#xff0c;go开发&#xff0c;你会特别注意内存和CPU的使用情况&#xff0c;那些对于CPU使用情况特别关注&#xff0c;或者性能特别关注的朋友可以看看这篇文章&#xff0c;相信看完结尾的示例…...

【Python】Python学习笔记(二)基本输入输出

Python娘来源&#xff1a;https://next.rikunabi.com/tech/docs/ct_s03600.jsp?p002412 目录print()函数不进行自动换行的print()函数打印输出多个字符串只进行换行input()函数使用format方法格式化字符串字符串与数值转换字符串转换为数值数值转换为字符串总结参考资料print(…...

LeetCode刷题系列 -- 724. 寻找数组的中心下标

给你一个整数数组 nums &#xff0c;请计算数组的 中心下标 。数组 中心下标 是数组的一个下标&#xff0c;其左侧所有元素相加的和等于右侧所有元素相加的和。如果中心下标位于数组最左端&#xff0c;那么左侧数之和视为 0 &#xff0c;因为在下标的左侧不存在元素。这一点对于…...

Linux编辑器vim

本文已收录至《Linux知识与编程》专栏&#xff01; 作者&#xff1a;ARMCSKGT 演示环境&#xff1a;CentOS 7 目录 前言 正文 vim常用方式 进入vim 退出vim vim基本模式及模式功能 命令模式 插入模式 底行模式 替换模式 视图模式 配置vim 自己配置vim 自动化配置…...

基于“python+”潮汐、风驱动循环、风暴潮等海洋水动力模拟

查看原文>>>基于“python”潮汐、风驱动循环、风暴潮等海洋水动力模拟ADCIRC是新一代海洋水动力计算模型&#xff0c;它采用了非结构三角形网格广义波动连续方程的设计&#xff0c;在提高计算精确度的同时还减小了计算时间。被广泛应用于&#xff1a;模拟潮汐和风驱动…...

《Terraform 101 从入门到实践》 第二章 Providers插件管理

《Terraform 101 从入门到实践》这本小册在南瓜慢说官方网站和GitHub两个地方同步更新&#xff0c;书中的示例代码也是放在GitHub上&#xff0c;方便大家参考查看。 不怕出身低&#xff0c;行行出状元。 插件 Terraform可以对多种平台的多种资源进行管理&#xff0c;这个是通过…...

03- pandas 数据库可视化 (机器学习)

pandas库的亮点: 一个快速、高效的DataFrame对象&#xff0c;用于数据操作和综合索引&#xff1b;用于在内存数据结构和不同格式之间读写数据的工具&#xff1a;CSV和文本文件、Microsoft Excel、SQL数据库和快速HDF 5格式&#xff1b;智能数据对齐和丢失数据的综合处理&#…...

Spring为什么这么火 之 Bean的6种作用域和Bean的生命周期

1、Bean的作用域 1.1、什么是作用域&#xff1f; 限定程序中变量的可用范围叫做作用域&#xff0c;或者说在源代码中定义变量的某个区域就叫做作用域 1.2、Bean的6种作用域 singleton&#xff1a;单例作用域prototype&#xff1a;原型作用域【多例作用域】request&#xff1…...

【CSS面试题】2023前端最新版css模块,高频15问

&#x1f973;博 主&#xff1a;初映CY的前说(前端领域) &#x1f31e;个人信条&#xff1a;想要变成得到&#xff0c;中间还有做到&#xff01; &#x1f918;本文核心&#xff1a;博主收集的CSS面试题 目录 一、CSS必备面试题 1.CSS3新特性 2.CSS实现元素两个盒子垂…...

SpringCloud-Netflix学习笔记10——Hystrix实现服务熔断

一、概述 1、分布式系统面临的问题 复杂分布式体系结构中的应用程序有数十个依赖关系&#xff0c;每个依赖关系在某些时候将不可避免的失败&#xff01; 2、服务雪崩 多个微服务之间调用的时候&#xff0c;假设微服务A调用微服务B和微服务C&#xff0c;微服务B 和微服务C又…...

精华文稿|迈向统一的点云三维物体检测框架

分享嘉宾 | 杨泽同 文稿整理 | William 嘉宾介绍 Introduction 3D检测是在三维世界中去定位和分类不同的物体&#xff0c;与传统2D检测的区别在于它有一个深度信息。目前&#xff0c;大部分的工作是倾向于用点云去做三维检测&#xff0c;点云实际上是通过传感器去扫描出来的一…...

面试题:Redis网络模型

1 用户空间和内核空间以Centos 7 linux操作系统为例。计算机系统被内核操控&#xff0c; 内核被应用操控。为了避免用户应用导致冲突甚至内核崩溃&#xff0c;用户应用与内核是分离的进程的寻址空间会划分为两部分:内核空间、用户空间。用户空间只能执行受限的命令(Rin3&#x…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...