P1969 [NOIP 2013 Senior] Building Blocks Contest

NOIP 2013 Senior D2T1.

Chun-Chun Kindergarten is holding its annual "Building Blocks Contest." This year, the task is to construct a building of width $n$, which can be regarded as composed of $n$ blocks each of width $1$. The final height of the $i$-th block should be $h_i$. Before construction starts, there are no blocks (equivalently, there are $n$ blocks of height $0$). In each operation, the children may choose a continuous interval $[L, R]$, and then increase by $1$ the height of every block from the $L$-th to the $R$-th (inclusive). Xiao M is a clever child and quickly figured out an optimal strategy that minimizes the number of operations. However, she is not keen on doing it herself, so she asks you to implement this strategy and compute the minimum number of operations.

There are two lines. The first line contains an integer $n$, the width of the building. The second line contains $n$ integers, where the $i$-th integer is $h_i$.

Output the minimum number of operations required to complete the construction.

Sample explanation: One optimal sequence is to choose: $[1, 5]$, $[1, 3]$, $[2, 3]$, $[3, 3]$, $[5, 5]$. Constraints: - For $30\%$ of the testdata, $1 \leq n \leq 10$. - For $70\%$ of the testdata, $1 \leq n \leq 1000$. - For $100\%$ of the testdata, $1 \leq n \leq 100000$, $0 \leq h_i \leq 10000$. Translated by ChatGPT 5