我的博客--土豆bcoi

Ai :)

• 豆包:逗堡
• 百度:摆渡
• 文心:蚊鑫

• 视频:bilibili 抖音

• excalidraw

• 工具
• 骗分导论【新版】@js25128

...

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

【基础】合唱队形求解

#include <bits/stdc++.h>
using namespace std;
int n,a[2005],l[10005],r[10005],z;
int main(){
	cin >> n;
	for(int i=1;i<=n;i++)cin >> a[i];
	for(int i=1;i<=n;i++){
		l[i]=1;
		for(int j=1;j<i;j++){
			if(a[j]<a[i])l[i]=max(l[i],l[j]+1);
		}
	}
	for(int i=n;i>=1;i--){
		r[i]=1;
		for(int j=i;j<=n;j++){
			if(a[j]<a[i])r[i]=max(r[i],r[j]+1);
		}
	}
	int maxn=INT_MIN;
	for(int i=1;i<=n;i++){
		z=l[i]+r[i]-1;
		maxn=max(maxn,z);
	}
	cout << n-maxn;
	return 0;
}