信息学奥赛一本通 1264:合唱队形(evd)
发布日期:2022-01-30 02:41:37 浏览次数:15 分类:技术文章

本文共 950 字,大约阅读时间需要 3 分钟。

【题目描述】

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

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

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

【输入】

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

【输出】

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

【输入样例】

8
186 186 150 200 160 130 197 220
【输出样例】
4
【提示】
对于50%的数据,保证有n≤20;

对于全部的数据,保证有n≤100。

【心得】经典题目,就是正着一遍LIS,反这再来一遍,算每个人两个方向的最值而已!
【AC代码】

#include
#include
#include
using namespace std;const int N=105;int h[N],l[N],r[N];int main(){
int n,ma=-1; cin>>n; for(int i=1;i<=n;i++) {
cin>>h[i]; l[i]=1; r[i]=1; } for(int i=n-1;i>=1;i--) {
for(int j=i+1;j<=n;j++) {
if(h[i]>h[j]&&r[i]<=r[j]) {
r[i]=r[j]+1; } } } for(int i=2;i<=n;i++) {
for(int j=1;j
h[j]&&l[i]<=l[j]) {
l[i]=l[j]+1; } } } for(int i=1;i<=n;i++) ma=max(ma,l[i]+r[i]-1); cout<

转载地址:https://blog.csdn.net/everwide1982/article/details/109798921 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:信息学奥赛一本通 1263:友好城市(evd)
下一篇:信息学奥赛一本通 1265:最长公共子序列(evd)

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2024年03月15日 04时56分02秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

mysql service5.7_Mysql5.7服务下载安装 2019-04-21
mysql查看线程完整执行命令_MySQL-查看运行的线程-SHOW PROCESSLIST 2019-04-21
mysql 更新数据 字符串_批量替换 MySQL 指定字段中的字符串 2019-04-21
web开发 mysql安装_mysqlinstallerwebcommunity5.7.21.0.msi安装图文教程 2019-04-21
mysql concat 整数型_MySQL 数字类型转换函数(concat/cast) 2019-04-21
mysql单元格函数是_MySQL常用内置函数 2019-04-21
mysql 怎么字段分裂_你可以分裂/爆炸MySQL查询中的字段吗? 2019-04-21
mysql server卸载出错_Mysql卸载问题Start Server卡住报错解决方法 2019-04-21
c语言课程设计工资管理建库,C语言课程设计工资管理系统参考.doc 2019-04-21
c语言case中途跳出,break语句在switch结构语句中的作用是终止某个case,并跳出switch结构语句。... 2019-04-21
C语言编写程序计算高考倒计时天数,基于51单片机LCD12864大字符校时万年历带高考倒计时程序... 2019-04-21
普职融通信息技术课本C语言,“三步走”扎实推进“普职融通”办学新模式 2019-04-21
Android多个签名,【Android】Android批量重签名 2019-04-21
html unicode编码转换,JS实现的Unicode编码转换操作示例 2019-04-21
html页面角落放动漫人物,L2Dwidget.js L2D网页动画人物添加 2019-04-21
html图片水平居中,CSS制作图片水平垂直居中 2019-04-21
php写模糊搜索api接口,php通过sphinxapi接口实现全文搜索 2019-04-21
oracle安装出现2932,【案例】Oracle报错ORA-19815 fast_recovery_area无剩余空间解决办法... 2019-04-21
form表单属性名相同java_form表单提交时候有多个相同name 的input如何处理? 2019-04-21
java图片加气泡文字_图片加气泡文字 2019-04-21