题解 | #合唱队#

/*
解题关键，找出最长子序列（LIS）
用两个哈希表存储meoleft[3000],meoright[3000]存储从i位置最长的升序，降序子序列
之后让ans[i] = n+1-meolrft[i]-meoright[i];
最后再遍历出最小值
*/

#include <stdio.h>

// 最大值
int Max(int a, int b)
{
    return a > b ? a : b;
}



int main() {
    int n;
    scanf("%d", &n);
    int peo[3000] = { 0 };
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &peo[i]);
    }
    int meoright[3000] = { 0 };
    int meoleft[3000] = { 0 };
    int ans[3000] = { 0 };
    

    for (int i = 0; i < n; i++)
    {
        meoright[i] = 1;
        meoleft[i] = 1;
        ans[i] = 0;
    }
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (peo[j] < peo[i])
            {
                meoleft[i] = Max(meoleft[i], meoleft[j] + 1);
            }
        }
    }
    for (int i = n-1; i >=0; i--)
    {
        for (int j = n-1; j > i; j--)
        {
            if (peo[j] < peo[i])
            {
                meoright[i] = Max(meoright[i],meoright[j]+1);
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        ans[i] = n+1 - meoleft[i] - meoright[i];
    }
    int min = n;
    for (int i = 0; i < n; i++)
    {
        if (ans[i] < min)
        {
            min = ans[i];
        }
    }

    printf("%d\n",min);
    return 0;
    
   
}