题目描述
n 位同学站成一排，音乐老师要请其中的 n-k 位同学出列，使得剩下的 k 位同学排成合唱队形。
合唱队形是指这样的一种队形：设 k 位同学从左到右依次编号为 1,2,…,k，他们的身高分别为 t1,t2,…,tk，则他们的身高满足 t1<…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。
解题思路
因为要求最少出列同学，所以间接说明在合唱队形中的人数越多越好。又要求中间必须是最高的，所以要从第一个人开始遍历，看看是否满足题意且上升序列的时候人数是最多的，下降序列的时候人数也是最多的。而既要遍历，又要人数最多，肯定是要进行最大值的替换。
动规五部曲：最重要的是递推公式。
1. DP 数组含义及下标含义
dp[i] 刚好可以表示成以 i 为最高的人时，上升序列或下降序列的人数。根据分析，就要定义两个数组来表示。即上述 b[i] 和 c[i]。 b[i] 表示以 i 结尾的最长上升子序列长度。 c[i] 表示以 i 开头的最长下降子序列长度（从右向左的上升子序列）。
2. 递推公式
利用已经计算好的子问题（b[j]）来解决当前问题（b[i]）。而刚计算好的 b[i] 又可以作为下一次的 b[j] 来计算。
if (a[i] > a[j] && b[j] + 1 > b[i]) {
b[i] = b[j] + 1;
}
怎么想到的递推公式呢？我们要求的是：以 i 结尾的最长上升子序列长度。 自然想法：
- 一个以 i 结尾的上升子序列=某个以 j 结尾的上升子序列+a[i]。注意，前面的某个以 j 结尾的上升子序列，不一定是 i-1=j，因为我们要取的是最大人数，所以肯定要选一个最合适的上升子序列，这个可能是任意一个。
- 要求：a[j] < a[i]（这样才能接上）
- 长度 = 那个子序列的长度 + 1
b[i] = max(b[j] + 1)，对于所有 j < i 且 a[j] < a[i]。
为什么这样想？
- 我们不知道哪个 j 最好，所以要枚举所有可能的 j。
- 对每个可能的 j，计算 b[j] + 1。
- 取最大值就是答案。
- 先假设最坏情况：b[i] = 1（只有自己）。
- 然后尝试改进：对每个 j，看看能不能让 b[i] 变大。
- 如果能接在 j 后面（a[i] > a[j]）。
- 而且接上后比当前记录的长度更长（b[j] + 1 > b[i]）。
- 就更新记录。
3. DP 数组如何进行初始化
那就只能根据实际意义来写了。因为我们要算的是人数是否是最大的，当 i 表示的那个人不符合题意时，肯定这个队列中只有这一个人，因为其他人都不符合题意都被去掉了，所以可以将每一次遍历时都初始化为 1，反正是最小的最大值，不会影响后面的判断。
4. 遍历顺序
很好理解。我就不分析了。
代码实现
#include <stdio.h>
#include
a[];
b[];
c[];
{
n;
(, &n);
(b, , (b));
(c, , (c));
( i = ; i <= n; i++) {
(, &a[i]);
}
( i = ; i <= n; i++) {
b[i] = ;
( j = ; j < i; j++) {
(a[i] > a[j] && b[j] + > b[i]) {
b[i] = b[j] + ;
}
}
}
( i = n; i >= ; i--) {
c[i] = ;
( j = i + ; j <= n; j++) {
(a[i] > a[j] && c[j] + > c[i]) {
c[i] = c[j] + ;
}
}
}
ans = ;
( i = ; i <= n; i++) {
(b[i] + c[i] > ans) {
ans = b[i] + c[i];
}
}
(, n - (ans - ));
;
}
