牛客 假日 13c
合唱队形
https://ac.nowcoder.com/acm/contest/1082/C
题目描述：给你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;
} 
阿里巴巴一面141人在聊
投递淘天集团等公司10个岗位 >