合唱队形

有一个跟这个很像的题是 CF739C，有兴趣的可以去做一做。

在这里定义

f_{i}

表示为以

i

结尾的最长上升子序列个数，

g_i

表示为以

i

开始的最长下降子序列个数，则显然当

f_i+g_i

最大时

i

为两者转接点。

此时考虑状态转移方程，即

f_i=\max_{a_j<a_i,j<i}f_j+1,g_i=\max_{a_j<a_i,j>i}g_j+1

。此时算出后答案为

\max_{i=1}^n n-f_i-g_i+1

。

code

CPP

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define lx first
#define ly second
const int maxn=1e2+10;
int n,a[maxn];
int f[maxn],ans=INT_MAX;
signed main(){
//	freopen("T2.in","r",stdin);
//	freopen("T2.out","w",stdout);
	cin >> n;for(int i=1;i<=n;++i)cin >> a[i];
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j)f[j]=1;
		for(int j=1;j<=i;++j){
			for(int k=1;k<j;++k){
				if(a[k]<a[j])f[j]=max(f[j],f[k]+1);
			}
		}
		int cnt1=f[i];
		for(int j=1;j<=n;++j)f[j]=1;
		for(int j=n;j>=i;--j){
			for(int k=n;k>j;--k){
				if(a[k]<a[j])f[j]=max(f[j],f[k]+1);
			}
		}
		cnt1+=f[i]-1;ans=min(ans,n-cnt1);
	}
	cout << ans << endl;
	return 0;
}

文章操作

code

相关推荐

评论

合唱队形