算法提高课汇总

算法思路

我们可以惊喜╰(*°▽°*)╯的发现, $K$位同学的合唱队形与AcWing 1014. 登山游览景点的形式一样.

题目求$N - K$的最小, 也即求符合这种形式的最大的$K$. 与登山相同解法.

代码实现

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int a[N];
int dp[N], udp[N];

int main()
{
    cin >> n;
    for( int i = 1; i <= n; i ++ )  cin >> a[i];

    for( int i = 1; i <= n; i ++ )
    {
        dp[i] = 1;
        for( int j = 1; j < i; j ++ )
            if( a[j] < a[i] )
            {
                dp[i] = max( dp[i], dp[j] + 1 );
            }
    }

    for( int i = n; i >= 1; i -- )
    {
        udp[i] = 1;
        for( int j = n; j > i; j -- )
            if( a[j] < a[i] )
            {
                udp[i] = max( udp[i], udp[j] + 1 );
            }
    }

    int res = 0;
    for( int i = 1; i <= n; i ++ )  res = max( res, dp[i] + udp[i] - 1 );

    cout << n - res << endl;
    return 0;
}