P2893 [USACO08FEB] Making the Grade G

Farmer John wants to renovate a road of length $N$. The original elevation of each segment is $A_i$, and after repair it becomes $B_i$, with a cost of $|A_i - B_i|$. We require the repaired road, that is, the sequence $B_i$ you construct, to be monotone nonincreasing or monotone nondecreasing. Find the minimum total cost $\sum_{i=1}^{N} |A_i - B_i|$.

The first line contains an integer $N$. The next $N$ lines each contain an integer $A_i$.

Output a single integer, the minimum cost.

Constraints: $1 \le N \le 2000$, $0 \le A_i \le 10^9$. Translated by ChatGPT 5