合唱队形

_shine_ · 2025-02-21 17:37:11 · 题解

有一个跟这个很像的题是 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

#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;
}