[CF1400E] Clear the Multiset - 贪心,分治

Description

给定一个长度为 \(n\) 的序列，每次可以选择一个区间 \([l,r]\) 将区间中的每个数 \(-1\)，或者选择一个位置 \(pos\) 和一个值 \(x\)，将第 \(pos\) 个位置的数减去 \(x\)。需要保持所有的数非负。求操作直到所有数变成 \(0\) 的最小代价。

Solution

分治贪心，递归求解。对于区间 \([l,r]\)，如果不用第一种操作那么答案就是区间长，如果用第一种操作，那么显然我们可以找到一个最小的位置 \(k\)，将区间中所有的数减去 \(a[k]\)，然后递归求解区间 \([l,k-1],[k+1,r]\)。

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 5005;

int n, a[N];

int f(int l, int r)
{
    if (l > r)
        return 0;
    if (l == r)
        return a[l] != 0;
    int minPos = min_element(a + l, a + r + 1) - a;
    int minVal = a[minPos];
    for (int i = l; i <= r; i++)
        a[i] -= minVal;
    return min(minVal + f(l, minPos - 1) + f(minPos + 1, r), r - l + 1);
}

signed main()
{
    ios::sync_with_stdio(false);

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

    cout << f(1, n) << endl;
    return 0;
}

[CF1400E] Clear the Multiset - 贪心,分治

原文：https://www.cnblogs.com/mollnn/p/13912770.html