合唱队形

题目描述

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学不交换位置就能排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK， 则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入描述

输入的第一行是一个整数N（2 <= N <= 100），表示同学的总数。
第一行有n个整数，用空格分隔，第i个整数Ti（130 <= Ti <= 230）是第i位同学的身高（厘米）。

输出描述

可能包括多组测试数据，对于每组数据，
输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

输入

8
186 186 150 200 160 130 197 220
输出

4

最长上升子序列

#include<bits/stdc++.h>
using namespace std;
int d[105], p[105], A[105];

int main(){
	int n; 
	while(cin>>n){
		for(int i=0;i<n;i++){
			cin >> A[i];
		}
		//从左往右最长上升
		for(int i=0;i<n;i++){
			d[i] = 1;
			for(int j=0;j<i;j++){
				if(A[j] < A[i] && d[j] + 1 > d[i]){
					d[i] = d[j] + 1;
				}
			}
		}
		//从右往左最长下降
		for(int i=n-1; i>=0; i--){
			p[i]=1;
			for(int j=i+1; j<n; j++){
				if(A[j] < A[i] && p[j] + 1 > p[i]){
					p[i] = p[j] + 1;
				}
			}
		} 
		int ans = 101;
		for(int i=0; i<n; i++){
			int t = d[i] + p[i] - 1; //满足队形的人数, i这个人计算了两次 所以减掉1 
			if(ans > n - t){
				ans = n- t; 
			} 
		}
		cout<<ans<<endl;
	}
	
	
	return 0;
}