Clear the Multiset (Codeforces 1400E)
Tags: Greedy, divide and conquer

You have a multiset containing several integers. Initially, it contains $$$a_1$$$ elements equal to $$$1$$$, $$$a_2$$$ elements equal to $$$2$$$, ..., $$$a_n$$$ elements equal to $$$n$$$.You may apply two types of operations:  choose two integers $$$l$$$ and $$$r$$$ ($$$l \le r$$$), then remove one occurrence of $$$l$$$, one occurrence of $$$l + 1$$$, ..., one occurrence of $$$r$$$ from the multiset. This operation can be applied only if each number from $$$l$$$ to $$$r$$$ occurs at least once in the multiset;  choose two integers $$$i$$$ and $$$x$$$ ($$$x \ge 1$$$), then remove $$$x$$$ occurrences of $$$i$$$ from the multiset. This operation can be applied only if the multiset contains at least $$$x$$$ occurrences of $$$i$$$. What is the minimum number of operations required to delete all elements from the multiset?

Input: The first line contains one integer $$$n$$$ ($$$1 \le n \le 5000$$$).The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_i \le 10^9$$$).

Output: Print one integer — the minimum number of operations required to delete all elements from the multiset.


Sample Inputs:
4
1 4 1 1

5
1 0 1 0 1

Sample Outputs:
2

3

Solution (Python):
from math import log2, inf

class SegmentTree:

    def __init__(self, array, func=max):
        self.n = len(array)
        self.size = 2 ** (int(log2(self.n - 1)) + 1) if self.n != 1 else 1
        self.func = func
        self.default = 0 if self.func != min else inf
        self.data = [self.default] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size:self.size + self.n] = array
        for i in range(self.size - 1, -1, -1):
            self.data[i] = self.func(self.data[2 * i], self.data[2 * i + 1])

    def query(self, alpha, omega):
        """"""
        if alpha == omega:
            return self.data[alpha + self.size]
        res = self.default
        alpha += self.size
        omega += self.size + 1
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res

    def update(self, index, value):
        """"""
        index += self.size
        self.data[index] = value
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2 * index], self.data[2 * index + 1])
            index >>= 1
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
    ans = 1
    for each in a:
        ans = ans * each % mod
    return ans

def lcm(a, b):
    return a * b // gcd(a, b)

def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else '0' * (length - len(y)) + y
import sys
sys.setrecursionlimit(10 ** 5)
for _ in range(int(input()) if not True else 1):
    n = int(input())
    a = list(map(int, input().split()))
    di = {}
    for i in range(n):
        if a[i] not in di:
            di[a[i]] = []
        di[a[i]] += [i]
    for i in di:
        di[i] = di[i][::-1]
    st = SegmentTree(a, func=min)

    def f(i, j, k=0):
        if i > j:
            return 0
        mi = st.query(i, j)
        index = di[mi].pop()
        return min(j - i + 1, mi - k + f(i, index - 1, max(mi, k)) + f(index + 1, j, max(mi, k)))
    print(f(0, n - 1))

Solution (Python):
import sys
sys.setrecursionlimit(10000)
n = int(input())
a = list(map(int, input().split()))

def solve(i, j, x):
    if i > j:
        return 0
    idx = a.index(min(a[i:j + 1]), i, j + 1)
    mn = a[idx]
    case = mn - x + solve(i, idx - 1, mn) + solve(idx + 1, j, mn)
    return min(case, j - i + 1)
print(solve(0, n - 1, 0))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def rec(l, r, sub):
    if l >= r:
        return 0
    m = a.index(min(a[l:r]), l, r)
    return min(r - l, a[m] - sub + rec(l, m, a[m]) + rec(m + 1, r, a[m]))
n = int(input())
a = list(map(int, input().split()))
print(rec(0, n, 0))