相当于求两个最长递增子序列吧。emmm,还没看大佬写的,暂且是这么个想法。

dp1[i]表示以a1[i]结尾的最长递增子序列

然后把a1[i]转置成a2[i],接着求以a2[i]为结尾的最长递增子序列dp2[i],(相当于求以a[i]为结尾的左边正序一个最长递增,后边倒序的一个最长递减)

然后对应的a1[i]和a2[n-1-i]相加起来,求得最大的 max

再用N-(max-1) 就是结果。

1 3 5 7 4 2 0
注意一定要减一,因为上面的例子, 1 3 5 7算了一次7,0 2 4 7也算了一次7

#include<iostream>
using namespace std;
const int maxn=100;
int a1[maxn],a2[maxn],dp1[maxn],dp2[maxn];
int main(){
    int n;
    while(cin>>n){
        for(int i=0;i<n;i++){
            cin>>a1[i];
            a2[n-1-i]=a1[i];
        }
        for(int i=0;i<n;i++){
            dp1[i]=1;dp2[i]=1;
            for(int j=0;j<i;j++){
                if(a1[j]<a1[i])
                    dp1[i]=max(dp1[i],dp1[j]+1);
                if(a2[j]<a2[i])
                    dp2[i]=max(dp2[i],dp2[j]+1);
            }
        }
        int res=0;
        for(int i=0;i<n;i++){
            dp1[i]+=dp2[n-1-i];
            res=max(res,dp1[i]);
        }
        cout<<n-res+1<<endl;
    }
    return 0;
}