N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TKT1,T2,…,TK, 则他们的身高满足T1<…<Ti>Ti+1>…>TK(1≤i≤K)。
你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
输入格式
输入的第一行是一个整数N,表示同学的总数。
第二行有n个整数,用空格分隔,第i个整数Ti是第i位同学的身高(厘米)。
输出格式
输出包括一行,这一行只包含一个整数,就是最少需要几位同学出列。
数据范围
2≤N≤100,
130≤Ti≤230
输入样例:
8
186 186 150 200 160 130 197 220
输出样例:
4
思路:枚举每个点作为Ti,求T0-Ti最长上升子序列长度len1和Tn-Ti的最长上升子序列长度len2 ,ans=min(n-len1-len2-1,ans) (LIS最长上升子序列问题朴素算法O(n^2),使用二分的话可以把复杂度降到O(nlogn))
#include<iostream>
#include<algorithm>
#include<vector>
#include<memory.h>
using namespace std;
int n;
int f[110],num[110];
int main(){
cin>>n;
int ans=231;
memset(f,0,sizeof f);
memset(num,0,sizeof num);
for(int i=0;i<n;i++) cin>>f[i];
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(f[j]<f[i]){
num[j]=1;
for(int k=0;k<j;k++){
if(f[k]<f[j] && num[k]+1>num[j]){
num[j]=num[k]+1;
}
}
}
}
int len1=0;
for(int p=0;p<i;p++){len1=max(len1,num[p]);}
memset(num,0,sizeof num);
for(int j=n-1;j>i;j--){
if(f[j]<f[i]){
num[j]=1;
for(int k=n;k>j;k--){
if(f[k]<f[j] && num[k]+1>num[j]){
num[j]=num[k]+1;
}
}
}
}
int len2=0;
for(int p=n-1;p>i;p--){len2=max(len2,num[p]);}
ans=min(ans,n-len1-len2-1);
//cout<<ans<<endl;
}
cout<<ans;
return 0;
}
简洁的代码如下 y总yyds:
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int w[N];
int f[N], g[N];
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> w[i];
for (int i = 1; i <= n; i ++ )
{
f[i] = 1;
for (int j = 1; j < i; j ++ )
if (w[i] > w[j])
f[i] = max(f[i], f[j] + 1);
}
for (int i = n; i; i -- )
{
g[i] = 1;
for (int j = n; j > i; j -- )
if (w[i] > w[j])
g[i] = max(g[i], g[j] + 1);
}
int res = 0;
for (int k = 1; k <= n; k ++ ) res = max(res, f[k] + g[k] - 1);
cout << n - res << endl;
return 0;
}