思路
分割成两个最长上升子序列问题,f[i]代表从左边开始,g[i]代表从右边开始;
最后不要忘记中间那个元素多算了一次;
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int h[N], f[N], g[N];
int main(){
int n;
cin >> n;
for(int i = 0; i < n; i++) cin >> h[i];
//计算左边的最长子序列
for(int i = 0; i < n; i++) {
f[i] = 1;
for(int j = 0; j < i; j++)
if(h[i] > h[j]) f[i] = max(f[i], f[j] + 1);
}
//计算右边的最长子序列
for(int i = n - 1; i; i--){
g[i] = 1;
for(int j = n - 1; j > i; j--)
if(h[i] > h[j]) g[i] = max(g[i], g[j] + 1);
}
int ans = 0;
for(int i = 0; i < n; i++) {
ans = max(ans, f[i] + g[i] - 1);//减去多算的那个
}
cout << n - ans << endl;
return 0;
}