信息学奥赛一本通 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年03月15日 04时56分02秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
mysql service5.7_Mysql5.7服务下载安装
2019-04-21
mysql 更新数据 字符串_批量替换 MySQL 指定字段中的字符串
2019-04-21
mysql concat 整数型_MySQL 数字类型转换函数(concat/cast)
2019-04-21
mysql单元格函数是_MySQL常用内置函数
2019-04-21
mysql 怎么字段分裂_你可以分裂/爆炸MySQL查询中的字段吗?
2019-04-21
c语言课程设计工资管理建库,C语言课程设计工资管理系统参考.doc
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
java图片加气泡文字_图片加气泡文字
2019-04-21