当前位置: 首页 > 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…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...