NOIP 真题解析：[NOIP 2004 提高组-T3] 合唱队形

[NOIP 2004 提高组-T3] 合唱队形摘要本题要求从一列同学中选出部分人排成先严格递增后严格递减的合唱队形求最少需要出列的同学人数。核心思路为对每个位置计算其左侧和右侧的最长上升子序列长度以d p l [ i ] d p r [ i ] − 1 dpl[i] dpr[i] - 1dpl[i]dpr[i]−1表示以i ii为峰点时最多可留下的人数最终结果为总人数n nn减去该最大值。题目描述n nn位同学站成一排音乐老师要请其中的n − k n-kn−k位同学出列使得剩下的k kk位同学排成合唱队形。合唱队形是指这样的一种队形设k kk位同学从左到右依次编号为1 , 2 , 1,2,1,2,…, k ,k,k他们的身高分别为t 1 , t 2 , t_1,t_2,t1​,t2​,…, t k ,t_k,tk​则他们的身高满足t 1 ⋯ t i t i 1 t_1 \cdots t_it_{i1}t1​⋯ti​ti1​… t k ( 1 ≤ i ≤ k ) t_k(1\le i\le k)tk​(1≤i≤k)。你的任务是已知所有n nn位同学的身高计算最少需要几位同学出列可以使得剩下的同学排成合唱队形。输入格式共二行。第一行是一个整数n nn2 ≤ n ≤ 100 2\le n\le1002≤n≤100表示同学的总数。第二行有n nn个整数用空格分隔第i ii个整数t i t_iti​130 ≤ t i ≤ 230 130\le t_i\le230130≤ti​≤230是第i ii位同学的身高厘米。输出格式一个整数最少需要几位同学出列。输入输出样例 #1输入 #18 186 186 150 200 160 130 197 220输出 #14说明/提示对于50 % 50\%50%的数据保证有n ≤ 20 n \le 20n≤20。对于全部的数据保证有n ≤ 100 n \le 100n≤100。思路要点本题要求一个最合适的 a[i]使得 [a[i] 左边 a[i] 的数的个数) (a[i] 右边 a[i] 的数个数) ] 最小。反过来想其实就是分别求 a[i] 左边从左往右的最长上升子序列设表示为 dpl[i]与 a[i] 右边从右往左的最长上升子序列设表示为 dpr[i]之和取其最大时的 a[i] 为峰点即可。此时留下来的人数为 dpl[i] dpr[i] - 1用总人数减去最多能留下来的人数即为所求最少出列同学人数。参考代码#includebits/stdc.husingnamespacestd;intn,a[105],dpl[105],dpr[105],maxn,ans;intmain(){cinn;for(inti1;in;i){cina[i];// 从左往右求一遍截至 a[i] 的最长上升子序列dpl[i]1;// 初始化 dpl[i] 为 1 (仅含 a[i] 的情况)for(intj1;ji;j){// 枚举 a[i] 左边的元素if(a[j]a[i]){dpl[i]max(dpl[i],dpl[j]1);}}}for(intin;i1;i--){// 从右往左求一遍截至 a[i] 的最长上升子序列dpr[i]1;// 初始化 dpr[i] 为 1 (仅含 a[i] 的情况)for(intjn;ji;j--){// 枚举 a[i] 右边的元素if(a[j]a[i]){dpr[i]max(dpr[i],dpr[j]1);}}// 若选 a[i] 为峰点能留下来的人数为 dpl[i] dpr[i] - 1maxnmax(maxn,dpl[i]dpr[i]-1);}ansn-maxn;// 最少出列学生数 总人数 - 最多留下的人数coutans;return0;}