C 解法, 执行用时: 2ms, 内存消耗: 328KB, 提交时间: 2021-09-22

#include <stdio.h>

int search_binary(int *nums,int top,int tgt)
{
    int mid;
    int left = 0,right = top;
    while(left <= right)
    {
        mid = (left + right)/2;
        if(tgt > nums[mid])
            left = mid+1;
        else
            right = mid-1;
    }
    return left;
}

void calc_dp(int N,int *nums,int *dp)
{
    int i;
    int top = 0;
    int stk[3072];
    stk[top] = nums[0];
    for(int i = 0; i < N; ++i)
    {
        if(nums[i] > stk[top])
        {
            stk[++top] = nums[i];
            dp[i] = top;
        }
        else
        {
            int pos = search_binary(stk,top,nums[i]);
            stk[pos] = nums[i];
            dp[i] = pos;
        }
    }
}

int main()
{
    int N;
    int max,tmp;
    int nums[3000];
    int dp_l[3072],dp_r[3072];
    while(scanf("%d", &N) != EOF)
    {
        for(int i = 0; i < N; i++)
        {
            scanf("%d",nums+i);
            dp_l[i] = dp_r[i] = 1; 
        }
        calc_dp(N,nums,dp_l);
        for(int i = 0,j = N-1; i < j; ++i,--j)
        {
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        calc_dp(N,nums,dp_r);
        max = 0;
        for(int i = 0,j=N-1; i < N; ++i,--j)
        {
            tmp = dp_l[i] + dp_r[j];
            max = tmp > max ? tmp : max; 
        }
        printf("%d\n",N-max-1);
    }
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2020-12-06

#include <stdio.h>

const int sz = 3072;
int search_binary(int *nums, int top, int tgt){
    int mi;
    int lo = 0;
    int hi = top;
    while(lo <= hi){
        mi = lo + (hi - lo) / 2;
        if(tgt > nums[mi]) lo = mi + 1;
        else hi = mi - 1;
    }
    return lo;
}
void calc_dp(int N, int *nums, int *dp){
    int i;
    int top = 0;
    int stk[sz];
    stk[top] = nums[0];
    for(i = 0; i < N; ++i){
        if(nums[i] > stk[top]){
            stk[++top] = nums[i];
            dp[i] = top;
        }
        else{
            int pos = search_binary(stk, top, nums[i]);
            stk[pos] = nums[i];
            dp[i] = pos;
        }
    }
}
int main(void){
    int max;
    int N;
    int tmp;
    int i, j;
    int nums[sz];
    int dp_d[sz];
    int dp_a[sz];
    while(scanf("%d", &N) == 1){
        for(i = 0; i < N; ++i){
            scanf("%d", nums + i);
            dp_d[i] = dp_a[i] = 1;
        }
        calc_dp(N, nums, dp_a);
        for(i = 0, j = N - 1; i < j; ++i, --j){
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        calc_dp(N, nums, dp_d);
        max = 0;
        for(i = 0, j = N-1; i < N; ++i, --j){
            tmp = dp_a[i] + dp_d[j];
            if(tmp > max) max = tmp;
        }
        printf("%d\n", N - max - 1);
    }
    return 0;
}