列举每一个小朋友当最高点,分左边和右边进行求最长上升子序列,取他们的最大值,最后减去用n减去最长上升子序列就行了
#include<iostream> #include<cstring> #include<algorithm> using namespace std ; const int N = 500; int f[N] ; int a[N] ; int b[N] ; int main(){ int n ; cin >> n ; for(int i = 1 ; i <= n ;i ++) cin >> a[i] ; for(int i = 1 ; i <= n ;i ++){ for(int j = 1 ; j <= i ; j ++) b[j] = a[j] ; int len = 0 ;int dp[N] ; memset(dp,0,sizeof(dp)) ; for(int k = 1 ; k <= i ; k ++){ dp[k] ++ ; for(int l = 1 ; l < k ;l ++ ){ if(b[k] > b[l]) dp[k] = max(dp[k],dp[l]+1) ; } } len += dp[i] ; memset(dp,0,sizeof(dp)) ; int cnt = 1 ; for(int j = n ; j >= i ; j--) b[cnt++] = a[j] ; cnt -- ; for(int k = 1 ; k <= cnt ; k ++){ dp[k] ++ ; for(int l = 1 ; l < k ;l ++ ){ if(b[k] > b[l]) dp[k] = max(dp[k],dp[l]+1) ; } } len += dp[cnt] ; len -- ; f[i] = len ; } int ans = 0 ; for(int i = 1 ; i <= n ; i++) ans = max(ans,f[i]) ; cout << n-ans << endl ; }