题目描述
N N N 位同学站成一排,音乐老师要请其中的 ( N − K ) (N-K) ( N − K ) 位同学出列,使得剩下的 K K K 位同学排成合唱队形。
合唱队形是指这样的一种队形:设 K K K 位同学从左到右依次编号为 1 , 2 , … , K 1,2,…,K 1 , 2 , … , K ,他们的身高分别为 T 1 , T 2 , … , T K T_1,T_2,…,T_K T 1 , T 2 , … , T K , 则他们的身高满足 $T_1<...< T_i >T_{i+1}>…>T_K(1 \le i \le K)$。
你的任务是,已知所有 N N N 位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
输入格式
共二行。
第一行是一个整数 N ( 2 ≤ N ≤ 100 ) N(2 \le N \le 100) N ( 2 ≤ N ≤ 100 ) ,表示同学的总数。
第二行有 n n n 个整数,用空格分隔,第 i i i 个整数 T i ( 130 ≤ T i ≤ 230 ) T_i(130 \le T_i \le 230) T i ( 130 ≤ T i ≤ 230 ) 是第 i i i 位同学的身高(厘米)。
输出格式
一个整数,最少需要几位同学出列。
输入输出样例
输入 #1
8
186 186 150 200 160 130 197 220
输出 #1
4
说明/提示
对于 50 % 50\% 50% 的数据,保证有 n ≤ 20 n \le 20 n ≤ 20 ;
对于全部的数据,保证有 n ≤ 100 n \le 100 n ≤ 100 。
分析
首先,要让最少的同学出列,就等价于让尽量多的同学留在队伍中。
观察到合唱队形满足 T 1 < . . . < T i > T i + 1 > … > T K ( 1 ≤ i ≤ K ) T_1<...< T_i >T_{i+1}>…>T_K(1 \le i \le K) T 1 < ... < T i > T i + 1 > … > T K ( 1 ≤ i ≤ K ) ,在合唱队形中,以第 i i i 个同学为分界点(分界点即为最高点),从 T 1 T_1 T 1 到 T i T_i T i 递增,从 T i T_i T i 到 T K T_K T K 递减。
设原队形中第 i i i 个同学的身高为 h e i g h t [ i ] height[i] h e i g h t [ i ] 。假设我们选取第 i i i 个同学作为合唱队形的最高点,那么要使尽量多的同学留在队伍中,合唱队形左边应该是 h e i g h t height h e i g h t 数组中从左到右以 h e g i h t [ i ] hegiht[i] h e g ih t [ i ] 结尾的 LIS \text{LIS} LIS ;右边应该是 h e g i h t hegiht h e g ih t 数组中从右到左以 h e i g h t [ i ] height[i] h e i g h t [ i ] 结尾的的 LIS \text{LIS} LIS 。
我们可以预处理出 h e i g h t height h e i g h t 数组中正向和逆向的最长上升子序列长度,然后枚举合唱队形的最高点,就可以得到最多能有多少同学留在队伍中,也就能知道最少需要几位同学出列。
设 l [ i ] l[i] l [ i ] 为从左到右以 h e i g h t [ i ] height[i] h e i g h t [ i ] 结尾的 LIS \text{LIS} LIS 长度,r [ i ] r[i] r [ i ] 为从右到左以 h e i g h t [ i ] height[i] h e i g h t [ i ] 为结尾的 LIS \text{LIS} LIS 长度。
有状态转移方程
l [ i ] = max 1 ≤ j < i ( l [ j ] + 1 ) × [ h e i g h t [ i ] > h e i g h t [ j ] ] l[i]=\max\limits_{1\le j<i}(l[j]+1)\times [height[i]>height[j]]
l [ i ] = 1 ≤ j < i max ( l [ j ] + 1 ) × [ h e i g h t [ i ] > h e i g h t [ j ]]
r [ i ] = max i < j ≤ n ( r [ j ] + 1 ) × [ h e i g h t [ i ] > h e i g h t [ j ] ] r[i]=\max\limits_{i< j\le n}(r[j]+1)\times [height[i]>height[j]]
r [ i ] = i < j ≤ n max ( r [ j ] + 1 ) × [ h e i g h t [ i ] > h e i g h t [ j ]]
当以 h e i g h t [ i ] height[i] h e i g h t [ i ] 为最高点时,能留在队伍中的同学个数为 l [ i ] + r [ i ] − 1 l[i]+r[i]-1 l [ i ] + r [ i ] − 1 。
因此,答案为 min 1 ≤ i ≤ n n − ( l [ i ] + r [ i ] − 1 ) \min\limits_{1\le i\le n}n-(l[i]+r[i]-1) 1 ≤ i ≤ n min n − ( l [ i ] + r [ i ] − 1 ) 。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 #include <iostream> #include <algorithm> #include <cstdio> #define N 103 using namespace std;int l[N],r[N];int height[N];int n,ans=0x3f3f3f3f ;int main () { int i; cin>>n; for (i=1 ;i<=n;i++) scanf ("%d" ,height+i); for (i=1 ;i<=n;i++) l[i]=r[i]=1 ; int j; for (i=2 ;i<=n;i++) { for (j=1 ;j<i;j++) { if (height[i]>height[j]) { l[i]=max (l[i],l[j]+1 ); } } } for (i=n-1 ;i>=1 ;i--) { for (j=n;j>i;j--) { if (height[i]>height[j]) { r[i]=max (r[i],r[j]+1 ); } } } for (i=1 ;i<=n;i++) ans=min (ans,n-(l[i]+r[i]-1 )); cout<<ans<<endl; return 0 ; }