问题描述
计算最少出列多少位同学,使得剩下的同学排成合唱队形说明:N位同学站成一排,音乐老师要请其中的(N-K)位同学出列,使得剩下的K位同学排成合唱队形。
合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK, 则他们的身高满足存在i(1<=i<=K)使得T1Ti+1>……>TK。
你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。
示例1
8
186 186 150 200 160 130 197 200
输出
4
求解思路
- 通过动态规划求解每个字符结尾的最大递增子字符串的长度,
- 再反转数组,
- 按照 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
using namespace std;
vector<int> dp(vector<int> &input,int n){
vector<int> list_(n,1);
for(int i=1;i<=n;i++)
for(int j=i-1;j>=0;j--){
if(input[i]>input[j])
list_[i]=max(list_[i],list_[j]+1);
}
return list_;
}
int main(){
int n;
while(cin>>n){
vector<int> input(n);
for(int i=0;i<n;i++){
cin>>input[i];
}
vector<int> front = dp(input,n);
reverse(input.begin(),input.end());
vector<int> back = dp(input, n);
int max_ = 0;
for(int i=0;i<n;i++){
int temp =front[i]+back[n-i-1];
if(temp>max_) max_=temp;
}
cout<<(n-(max_-1))<<endl;
}
return 0;
}