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