#P1091. [NOIP2004 提高组] 合唱队形

    ID: 318 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp2004单调队列NOIp 提高组

[NOIP2004 提高组] 合唱队形

题目描述

nn 位同学站成一排,音乐老师要请其中的 nkn-k 位同学出列,使得剩下的 kk 位同学排成合唱队形。

合唱队形是指这样的一种队形:设 kk 位同学从左到右依次编号为 1,2,1,2,,k,k,他们的身高分别为 t1,t2,t_1,t_2,,tk,t_k,则他们的身高满足 t1<<ti>ti+1>t_1< \cdots <t_i>t_{i+1}>>tk(1ik)>t_k(1\le i\le k)

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

输入格式

共二行。

第一行是一个整数 nn2n1002\le n\le100),表示同学的总数。

第二行有 nn 个整数,用空格分隔,第 ii 个整数 tit_i130ti230130\le t_i\le230)是第 ii 位同学的身高(厘米)。

输出格式

一个整数,最少需要几位同学出列。

8
186 186 150 200 160 130 197 220
4

提示

对于 50%50\% 的数据,保证有 n20n \le 20

对于全部的数据,保证有 n100n \le 100