华为机试题——合唱团

jiaxp

题目描述

计算最少出列多少位同学，使得剩下的同学排成合唱队形

说明：

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，   则他们的身高满足存在i（1<=i<=K）使得T1<T2<......<Ti-1<Ti>Ti+1>......>TK。

      你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入描述:

整数N

输出描述:

最少需要几位同学出列

输入例子:

8

186 186 150 200 160 130 197 200

输出例子:

4


#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int DeleteNum(vector<int> &vec);
int main() {
int N;
cin >> N;
vector<int> vec;
for (int i = 0; i < N; ++i) {
int height;
cin >> height;
vec.push_back(height);
}
vector<int> DelNum(N, 0);
for (int i = 0; i < N; ++i) {
vector<int> Left;
vector<int> Right;
for (int k = 0; k < N; ++k) {
if (k <= i)
Left.push_back(vec[k]);
if (k >= i)
Right.push_back(vec[k]);
}
reverse(Right.begin(), Right.end());
DelNum = DeleteNum(Left) + DeleteNum(Right);
}
int min = DelNum[0];
for (int i = 0; i < N; ++i) {
if (min > DelNum)
min = DelNum;
}
cout << min << endl;
return 0;
}
int DeleteNum(vector<int> &vec) {
if (vec.size() == 1)
return 0;
vector<int> f(vec.size(), 0);
int N = vec.size();
f[0] = 1;
for (int i = 0; i < N; ++i) {
f = 1;
for (int j = 0; j < i; ++j) {
if (vec[j] < vec && f[j] > f - 1)
f = f[j] + 1;
}
}
return N - f[N - 1];
}