【第74题】继续刷动态规划，[NOIP2004 提高组] 合唱队形，AC掉没商量

小码匠

发布于 2023-08-31 15:27:20

2740

发布于 2023-08-31 15:27:20

文章被收录于专栏：小码匠和老码农

【第74题】继续刷动态规划，[NOIP2004 提高组] 合唱队形，AC掉没商量

题目

题目原文请移步下面的链接

https://www.luogu.com.cn/problem/P1091
- 参考题解：https://www.luogu.com.cn/problem/solution/P1091
标签：OI、动态规划

题面

题目描述

n 位同学站成一排，音乐老师要请其中的n−k 位同学出列，使得剩下的 k 位同学排成合唱队形。

合唱队形是指这样的一种队形：设 k 位同学从左到右依次编号为 1,2, … ,k，他们的身高分别为，则他们的身高满足t_1<⋯t_{i+1}> … >t_k(1≤i≤k)

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

输入格式

共二行。

第一行是一个整数 n（2≤n≤100），表示同学的总数。

第二行有 n 个整数，用空格分隔，第 i 个整数

t_i

（130≤

t_i

≤230）是第 i 位同学的身高（厘米）。

输出格式

一个整数，最少需要几位同学出列。

输入输出样例

输入 #1复制

8
186 186 150 200 160 130 197 220

输出 #1复制

说明/提示

对于 50% 的数据，保证有 n≤20。

对于全部的数据，保证有 n≤100。

正解

先预处理对于每个

a_i

为开头/结尾的单调递增/递减序列，然后再枚举每个

a_i

作为“峰”（就是队形里最大的那个）时的最大价值，即ans=max(ans,

inc_i

dec_i

- 1)，因为在我们预处理时i这个位置上的值算了两次，所以要减去一次

AC代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>

using namespace std;
#define endl '\n';

void best_coder() {
    int n;
    cin >> n;
    vector<int> inc(n + 1);
    vector<int> dec(n + 1);
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        inc[i] = 1;
        dec[i] = 1;
    }
    for (int i = n - 1; i >= 1; --i) {
        for (int j = i + 1; j <= n; ++j) {
            if (a[i] > a[j] && inc[i] <= inc[j] + 1) {
                inc[i] = inc[j] + 1;
            }
        }
    }
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j < i; ++j) {
            if (a[i] > a[j] && dec[i] <= dec[j] + 1) {
                dec[i] = dec[j] + 1;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, inc[i] + dec[i] - 1);
    }
    cout << n - ans;
}

void happy_coder() {
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-08-05，如有侵权请联系 cloudcommunity@tencent.com 删除

include