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

动态规划DP 最长上升子序列模型 合唱队形(题目分析+C++完整代码)

概览检索
动态规划DP 最长上升子序列模型

合唱队形

原题链接

AcWiing 482. 合唱队形

题目描述

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

合唱队形是指这样的一种队形:设 K位同学从左到右依次编号为 1,2…,K,他们的身高分别为 T1,T2,…,TK,
则他们的身高满足 T1<…Ti+1>…>TK(1≤i≤K)。

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

输入格式
输入的第一行是一个整数 N,表示同学的总数。
第二行有 N个整数,用空格分隔,第 i个整数 Ti是第 i 位同学的身高(厘米)。

输出格式
输出包括一行,这一行只包含一个整数,就是最少需要几位同学出列。

数据范围
2≤N≤100,130≤Ti≤230

输入样例:

8
186 186 150 200 160 130 197 220

输出样例:

4

题目分析

由合唱队形满足的要求 身高满足 T1<…Ti+1>…>TK 可知该队形就是一个先上升后下降的子序列
最少去掉的同学 即使合唱队形中的人数最多
由此联想到 登山(点击链接跳转题目)。
也可参考 怪盗基德的滑翔伞(点击链接跳转题目)。

以最高的同学为划分,划分为左半部分的递增子序列,和右半部分的递减子序列(也就是相当于逆着的递增子序列),可直接看出该题为最长上升子序列模型。
分别求出左半部分和右半部分在以不同同学为那个顶峰时的值,分别存储在 f[i], g[i] 中。
则对应一个顶峰同学为i的合唱队形下的人数为 f[i]+g[i]-1 ,
遍历所有1~n的可能情形下,取其中人数最多(数值最大)的值max,
则出列的最少同学的数目为总人数n 减去该最大值max。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=110;
int n;
int a[N],f[N],g[N];
int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);//左半部分递增子序列for(int i=1;i<=n;i++){f[i]=1;  //序列中只有a[i],长度为1//前一个数为a[j]for(int j=1;j<i;j++)if(a[j]<a[i])  //满足前一个数a[j]大于后一个数a[i]f[i]=max(f[i],f[j]+1);  //尝试更新,f[j]+1为以前一个数a[j]结尾的最长序列的长度f[j]再加上当前最有一个数a[i](长度为1)}//右半部分递减子序列for(int i=n;i>=1;i--){g[i]=1;for(int j=n;j>i;j--)if(a[j]<a[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);  //取和的最大值printf("%d",n-res);  //所有人数-最大值return 0;
}

相关文章:

动态规划DP 最长上升子序列模型 合唱队形(题目分析+C++完整代码)

概览检索 动态规划DP 最长上升子序列模型 合唱队形 原题链接 AcWiing 482. 合唱队形 题目描述 N位同学站成一排&#xff0c;音乐老师要请其中的 (N−K)位同学出列&#xff0c;使得剩下的 K位同学排成合唱队形。 合唱队形是指这样的一种队形&#xff1a;设 K位同学从左到右…...

【踩坑】解决Hugging-face下载问题

解决Hugging-face下载问题 问题1&#xff1a;couldnt connect to https://huggingface.co问题2&#xff1a;HTTPSConnectionPool(hostcdn-lfs-us-1.hf-mirror.com, port443)设置hf_transfer加快速度 问题3&#xff1a;requests.exceptions.ChunkedEncodingError: (Connection b…...

Spring AI 在微服务中的应用:支持分布式 AI 推理

1. 引言 在现代企业中&#xff0c;微服务架构 已成为开发复杂系统的主流方式&#xff0c;而 AI 模型推理 也越来越多地被集成到业务流程中。如何在分布式微服务架构下高效地集成 Spring AI&#xff0c;使多个服务可以协同完成 AI 任务&#xff0c;并支持分布式 AI 推理&#x…...

5.3.2 软件设计原则

文章目录 抽象模块化信息隐蔽与独立性衡量 软件设计原则&#xff1a;抽象、模块化、信息隐蔽。 抽象 抽象是抽出事物本质的共同特性。过程抽象是指将一个明确定义功能的操作当作单个实体看待。数据抽象是对数据的类型、操作、取值范围进行定义&#xff0c;然后通过这些操作对数…...

java求职学习day20

1 在线考试系统 1.1 软件开发的流程 需求分析文档、概要设计文档、详细设计文档、编码和测试、安装和调试、维护和升级 1.2 软件的需求分析 在线考试系统的主要功能分析如下&#xff1a; &#xff08; 1 &#xff09;学员系统 &#xff08;1.1&#xff09;用户模块&…...

Python NumPy(8):NumPy 位运算、NumPy 字符串函数

1 NumPy 位运算 位运算是一种在二进制数字的位级别上进行操作的一类运算&#xff0c;它们直接操作二进制数字的各个位&#xff0c;而不考虑数字的整体值。NumPy 提供了一系列位运算函数&#xff0c;允许对数组中的元素进行逐位操作&#xff0c;这些操作与 Python 的位运算符类似…...

日志2025.1.30

日志2025.1.30 1.简略地做了一下交互系统 public class Interactable : MonoBehaviour { private MeshRenderer renderer; private Material defaultMaterial; public Material highlightMaterial; private void Awake() { renderer GetComponentInChildren<Me…...

实战:如何快速让新网站被百度收录?

本文来自&#xff1a;百万收录网 原文链接&#xff1a;https://www.baiwanshoulu.com/22.html 要让新网站快速被百度收录&#xff0c;可以采取以下实战策略&#xff1a; 一、网站基础优化 网站结构清晰&#xff1a;确保网站的结构简洁清晰&#xff0c;符合百度的抓取规则。主…...

PhotoShop中JSX编辑器安装

1.使用ExtendScript Tookit CC编辑 1.安装 打开CEP Resource链接&#xff1a; CEP-Resources/ExtendScript-Toolkit at master Adobe-CEP/CEP-Resources (github.com) 将文件clone到本地或者下载到本地 点击AdobeExtendScriptToolKit_4_Ls22.exe安装&#xff0c;根据弹出的…...

01-时间与管理

时间与效率 一丶番茄时钟步骤好处 二丶86400s的财富利用时间的方法每天坚持写下一天计划 自我管理体系计划-行动-评价-回顾 一丶番茄时钟 一个计时器 一份任务清单,任务 步骤 每一个25分钟是一个番茄时钟 将工作时间划分为若干个25分钟的工作单元期间只专注于当前任务,遇到…...

MiniMax-01技术报告解读

刚刚MiniMax发布了MiniMax-01&#xff0c;简单测试了效果&#xff0c;感觉不错。于是又把它的技术报告看了一下。这种报告看多了&#xff0c;就会多一个毛病&#xff0c;越来越觉得自己也能搞一个。 这篇文章我觉得最有意思的一句是对数据质量的强调“低质量数据在训练超过两个…...

多头潜在注意力(MLA):让大模型“轻装上阵”的技术革新——从DeepSeek看下一代语言模型的高效之路

多头潜在注意力&#xff08;MLA&#xff09;&#xff1a;让大模型“轻装上阵”的技术革新 ——从DeepSeek看下一代语言模型的高效之路 大模型的“内存焦虑” 当ChatGPT等大语言模型&#xff08;LLM&#xff09;惊艳世界时&#xff0c;很少有人意识到它们背后隐藏的“内存焦虑”…...

哈希表实现

目录 1. 哈希概念 1.1 直接定址法 1.2 哈希冲突 1.3 负载因子 1.4 将关键字转为整型 1.5 哈希函数 1.5.1 除法散列法/除留余数法 1.5.2 乘法散列法 1.5.3 全域散列法 1.5.4 其他方法 1.6 处理哈希冲突 1.6.1 开放定址法 1.6.1.1 线性探测 1.6.1.2 二次探测 1.6.…...

Linux的常用指令的用法

目录 Linux下基本指令 whoami ls指令&#xff1a; 文件&#xff1a; touch clear pwd cd mkdir rmdir指令 && rm 指令 man指令 cp mv cat more less head tail 管道和重定向 1. 重定向&#xff08;Redirection&#xff09; 2. 管道&#xff08;Pipes&a…...

Ubuntu安装VMware17

安装 下载本文的附件&#xff0c;之后执行 sudo chmod x VMware-Workstation-Full-17.5.2-23775571.x86_64.bundle sudo ./VMware-Workstation-Full-17.5.2-23775571.x86_64.bundle安装注意事项&#xff1a; 跳过账户登录的办法&#xff1a;断开网络 可能出现的问题以及解决…...

什么是线性化PDF?

线性化PDF是一种特殊的PDF文件组织方式。 总体而言&#xff0c;PDF是一种极为优雅且设计精良的格式。PDF由大量PDF对象构成&#xff0c;这些对象用于创建页面。相关信息存储在一棵二叉树中&#xff0c;该二叉树同时记录文件中每个对象的位置。因此&#xff0c;打开文件时只需加…...

每日一题——序列化二叉树

序列化二叉树 BM39 序列化二叉树题目描述序列化反序列化 示例示例1示例2 解题思路序列化过程反序列化过程 代码实现代码说明复杂度分析总结 BM39 序列化二叉树 题目描述 请实现两个函数&#xff0c;分别用来序列化和反序列化二叉树。二叉树的序列化是将二叉树按照某种遍历方式…...

Transformer+vit原理分析

目录 一、Transformer的核心思想 1. 自注意力机制&#xff08;Self-Attention&#xff09; 2. 多头注意力&#xff08;Multi-Head Attention&#xff09; 二、Transformer的架构 1. 整体结构 2. 编码器层&#xff08;Encoder Layer&#xff09; 3. 解码器层&#xff08;Decoder…...

「AI学习笔记」深度学习的起源与发展:从神经网络到大数据(二)

深度学习&#xff08;DL&#xff09;是现代人工智能&#xff08;AI&#xff09;的核心之一&#xff0c;但它并不是一夜之间出现的技术。从最初的理论提出到如今的广泛应用&#xff0c;深度学习经历了几乎一个世纪的不断探索与发展。今天&#xff0c;我们一起回顾深度学习的历史…...

【漫话机器学习系列】069.哈达马乘积(Hadamard Product)

哈达马乘积&#xff08;Hadamard Product&#xff09; 哈达马乘积&#xff08;Hadamard Product&#xff09;是两个矩阵之间的一种元素级操作&#xff0c;也称为逐元素乘积&#xff08;Element-wise Product&#xff09;。它以矩阵的对应元素相乘为规则&#xff0c;生成一个新…...

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明

LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造&#xff0c;完美适配AGV和无人叉车。同时&#xff0c;集成以太网与语音合成技术&#xff0c;为各类高级系统&#xff08;如MES、调度系统、库位管理、立库等&#xff09;提供高效便捷的语音交互体验。 L…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...