最长递增子序列

相当于求两个最长递增子序列吧。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;
}