题解
这题实际上就是一个最长上升子序列的板子题,只不过是求两次,最长上升子序列我们可以使用二分或者树状数组来进行优化,下面是C++的lower_bound
的用法, 它可以找到第一个大于等于key
的位置。
我们从左边开始求最长上升子序列,再从右边求最长上升子序列,下标idx1
和idx2
是这两个子序列的长度。
最后答案就是 n - ans + 1
,(减1是因为最大的值被算了2次)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int dp1[N], dp2[N], arr[N];
int n, ans;
int main() {
cin >> n;
for(int i = 1; i <= n; i++) cin >> arr[i];
for(int i = 1; i <= n; i++) {
int idx1 = 1, idx2 = 1;
dp1[1] = arr[1], dp2[1] = arr[n];
// 处理左边
for(int j = 2; j <= i; j++) {
if(arr[j] > dp1[idx1]) dp1[++idx1] = arr[j];
else {
int pos = lower_bound(dp1 + 1, dp1 + idx1, arr[j]) - dp1;
dp1[pos] = arr[j];
}
}
// 处理右边
for(int j = n - 1; j >= i; j--) {
if(arr[j] > dp2[idx2]) dp2[++idx2] = arr[j];
else {
int pos = lower_bound(dp2 + 1, dp2 + idx2, arr[j]) - dp2;
dp2[pos] = arr[j];
}
}
ans = max(ans, idx1 + idx2);
}
cout << n - ans + 1 << endl;
return 0;
}