题目描述:给你n个数要求你挑出尽可能少的几个数使得前半部分递增后半部分递减
n<130
分析:看数据范围可以看出来肯定是直接暴力,暴力每个点往前能构成的最长子序列,和往后的最长递减子序列,
            然后问题就是如何找最长递增(或递减)子序列, 考虑到一个最长子序列肯定是之前的最长子序列加一 所以记录下之前的就一定能找到后面的(非常像dp)
ac代码:
#include<iostream>
#include<cmath>
using namespace std;
int main(){
	int a[105];
	int al[105]={0},ar[105]={0};
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(a[i]>a[j]) al[i]=max(al[i],al[j]+1);
		}
	}
	for(int i=n;i>=1;i--)for(int j=n;j>i;j--) if(a[i]>a[j]) 
		ar[i]=max(ar[i],ar[j]+1);
	int ans=0;
	for(int i=1;i<=n;i++) {
		ans=max(ans,ar[i]+al[i]);
	}
	cout<<n-1-ans<<endl;
}