题解 | #合唱队#

#include <stdio.h>
void dp_inc(int* arr, int begin, int end, int* dp, int* stk) {
    int i = begin + 1, max = 1;
    dp[begin] = 1, stk[0] = -1, stk[1] = arr[begin];
    while (i <= end) {
        int pos = max;
        while (!(arr[i] > stk[pos]))pos--;//linear search
        max += pos++ == max;
        dp[i] = pos;
        stk[pos] = arr[i];
        i++;         
    }
}
int main()
{
    int n, arr[3000], dp[3000], dp_[3000],stk[3001], max = 0;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++)  scanf("%d", arr + i);
        dp_inc(arr, 0, n-1, dp, stk);
        for (int i = 0; i <= n - 1 >>1; i++) {
            int temp= arr[n - 1 - i];
            arr[n - 1 - i] = arr[i];
            arr[i] = temp;
        }
        dp_inc(arr, 0, n - 1, dp_, stk);
        max = 0;
        for (int i = 0; i < n; i++)
            max = max > dp[i] + dp_[n - 1-i] ? max : dp[i] + dp_[n - 1-i];
        printf("%d\n", n - max+1);
    }
}