nowcoder-HJ-24

HJ-24.

发布日期: 2022-06-22

HJ24 合唱队

1 题目描述

题目链接：HJ24 合唱队

N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形。

设KK位同学从左到右依次编号为 1，2…，K ，他们的身高分别为 $T_1,T_2,…,T_K$ ，若存在i($1\leq i\leq K$)使得 $T_1T_{i+1}>……>T_K$，则称这K名同学排成了合唱队形。
通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。

例子：
123 124 125 123 121 是一个合唱队形
123 123 124 122不是合唱队形，因为前两名同学身高相等，不符合要求
123 122 121 122不是合唱队形，因为找不到一个同学，他的两侧同学身高递减。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

注意：不允许改变队列元素的先后顺序且不要求最高同学左右人数必须相等

数据范围： $1 \le n \le 3000$

输入描述：

用例两行数据，第一行是同学的总数 N ，第二行是 N 位同学的身高，以空格隔开

输入描述：

最少需要几位同学出列

示例1：

输入: 8
186 186 150 200 160 130 197 200
输出: 4
说明:
由于不允许改变队列元素的先后顺序，所以最终剩下的队列应该为186 200 160 130或150 200 160 130

2 思路

采用了递增子序列的思路，分别从两端求取自末端到自身的连续子数组中小于自身的数，即求从两端到自身的子数组中最长递增子序列长度。然后对应位相加再减去1即为以某一位为中心的合法“队列”长度。

首先，定义数组dp1[i]，其意义为0-i的范围内的最长递增子序列长度，很明显，应该初始化为1，因为如果只有一个元素那它也是递增子序列，只是长度为1而已。更新的话，需要在0-i的范围内找小于vec[i]的元素，当找到vec[j] < vec[i]时，则dp1[i]应该更新为dp1[j]+1，因为dp1[j]就是0-j范围内的递增子序列最长长度，而dp1[i]的值最少也比dp1[j]大1，也就是多了vec[i]这一项，而当j-i之间还有值是介于vec[j]和vec[i]之间则需要继续更新。那么dp1[i]的更新公式就是：

$\begin{equation*} \begin{cases} dp1[i] = 1 \quad if \; vec[i] < vec[j] \; \forall j < i\\ dp1[i] = dp[j]+1 \quad if \; vec[i] > vec[j] \; \exists j < i \end{cases} \end{equation*}$

从右端的“递增子序列”也是一样的求法。这样求得的递增子序列其实就是以当前位为中心，左侧(右侧)形成递增序列的最多人数；那么两个数组的对应位相加就是以当前位为中心，左右两侧均为递增序列的最长长度（实际上算了自身两次，因而相加时需要-1）,最后返回数组最大值即可。

#include <iostream>
#include <vector>       
#include <cmath>        // max、min
#include <string.h>     // memset
using namespace std;

int main(void){
    int n, elem;
    cin >> n;
    vector<int> vec;
    for(int i = 0; i < n; ++i){
        cin >> elem;
        vec.emplace_back(elem);
    }
    vector<int> dp1(n, 1), dp2(n, 1);
    // 左边递增子序列
    for(int i = 1; i < n; ++i){
        for(int j = 0; j < i; ++j){
            if(vec[j] < vec[i]){
                dp1[i] = max(dp1[i], dp1[j]+1);
            }
        }
    }
    // 右边递增子序列
    for(int i = n-2; i >= 0; --i){
        for(int j = n-1; j > i; --j){
            if(vec[j] < vec[i]){
                dp2[i] = max(dp2[i], dp2[j]+1);
            }
        }
    }
    // 答案即为二者加和中的最大值
    int ans = 0;
    for(int i = 0; i < n; ++i){
        ans = max(ans, dp1[i] + dp2[i] - 1);
    }
    cout << n - ans << endl;
    return 0;
}