做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2419. -- [C++一本通-动态规划]例9.8 合唱队形

2419: [C++一本通-动态规划]例9.8 合唱队形

时间限制: 1 Sec  内存限制: 128 MB
提交: 93  解决: 49
[上一题][提交][讨论版][状态][下一题]

题目描述

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

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

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

输入

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

输出

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

样例输入

8
186 186 150 200 160 130 197 220

样例输出

4

提示

50%的数据满足:n<=20,全部的数据满足:n<=100.

标签

[上一题][提交][讨论版][状态][下一题]