[NOIP 2004 提高组] 合唱队形
题目描述
\(n\) 位同学站成一排，音乐老师要请其中的 \(n-k\) 位同学出列，使得剩下的 \(k\) 位同学排成合唱队形。
合唱队形是指这样的一种队形：设 \(k\) 位同学从左到右依次编号为 \(1,2,\) … \(,k\)，他们的身高分别为 \(t_1,t_2,\) … \(,t_k\)，则他们的身高满足 \(t_1< \cdots <t_i>t_{i+1}>\) … \(>t_k(1\le i\le k)\)。
你的任务是，已知所有 \(n\) 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入格式
\(\boxed{\begin{array}&n\\a_{1}&a_{2}&\dots&a_{n}\end{array}}\) 共二行。
第一行是一个整数 \(n\)（\(2\le n\le100\)），表示同学的总数。
第二行有 \(n\) 个整数，用空格分隔，第 \(i\) 个整数 \(t_i\)（\(130\le t_i\le230\)）是第 \(i\) 位同学的身高（厘米）。
输出格式
一个整数，最少需要几位同学出列。
样例 #1
样例输入 #1
1 | 8 |
样例输出 #1
1 | 4 |
Solution
- 从右往左，按左高右低顺序找出每一个位置右边有几个从高到低的数，即为 f[i]（包括自己）
- 从左往右，按左低右高顺序找出每一个位置左边有几个从低到高的数即为 g[i]（包括自己）
- 接着就可以把自己左边的从低到高的数和右边从高到低的数相加 -1 取最大值