两趟最长上升子序列dp,枚举中间的人求队伍长度最大值,然后总人数减去它就行了.
code:
#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
#define maxn 0x3f3f3f3f
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;
int n;
int a[105];
int dp1[105];
int dp2[105];
int ans;
int main() {
// clock_t start,end;
// start=clock();
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n; ++i) {
dp1[i]=1;
for (int k = 1; k < i; ++k) {
if (a[k] < a[i]) {
dp1[i] = max(dp1[k] + 1, dp1[i]);
}
}
}
for (int j = n; j >= 1; --j) {
dp2[j]=1;
for (int k = n; k >= j; --k) {
if (a[k] < a[j]) {
dp2[j] = max(dp2[k] + 1, dp2[j]);
}
}
}
for(int i=1;i<=n;++i){
ans=max(ans,dp1[i]+dp2[i]-1);
}
cout << n-ans << endl;
// end=clock();
// cout<<"TIME PASSED:"<<end-start<<endl;
return 0;
}