CF 1400E Clear the Multiset

题目描述

https://codeforces.com/contest/1400/problem/E

Solution

由于操作 $1$ 和操作 $2$ 可以交换，所以我们考虑先使用操作 $1$，然后再用操作 $2$ 去掉非零位置即可

然后我们能够想到一个简单的贪心

不妨假设我们现在操作的区间是 $[l,r]$，如果我们要使用操作 $1$，那么整个区间使用不会更劣（不妨假设可以使用

然后我们注意到我们这个时候需要使用操作 $1$，也就是说要用操作 $1$ 将某些数字变成 $0$，所以我们尽可能使用操作 $1$ 一定不会更劣

于是我们每次使用操作 $1$ 将整个区间减去其最小数，然后对于剩下的区间分治处理即可

#include <iostream>
#include <cstdio>
#include <algorithm> 
#define maxn 5010
using namespace std;

int n, a[maxn], pre[maxn], suf[maxn];

int solve(int l, int r) {
    if (l > r) return 0;
    int p = min_element(a + l, a + r + 1) - a, v = a[p];
    for (int i = l; i <= r; ++i) a[i] -= v; 
    return min(r - l + 1, solve(l, p - 1) + solve(p + 1, r) + v); 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cout << solve(1, n) << "\n"; 
    return 0;
}