P7994 [USACO21DEC] Air Cownditioning B

Farmer John’s $N$ cows are very picky about the temperature inside their barn. Some cows like it cooler, while others like it warmer. Farmer John’s barn contains a row of $N$ stalls, numbered $1 \ldots N$, with one cow in each stall. The $i$-th cow wants the temperature in her stall to be $p_i$, but the current temperature in her stall is $t_i$. To make sure every cow feels comfortable, Farmer John installed a new air-conditioning system. The way this system is controlled is quite special: he can send a command to the system telling it to increase or decrease the temperature of a continuous group of stalls by 1 unit—for example, “increase the temperature of stalls $5 \ldots 8$ by 1 unit.” A continuous group of stalls can be as short as a single stall. Please help Farmer John find the minimum number of commands he must send to the new air-conditioning system so that every stall’s temperature matches the ideal temperature of the cow in that stall.

The first line contains $N$. The next line contains $N$ non-negative integers $p_1 \ldots p_N$, separated by spaces. The last line contains $N$ non-negative integers $t_1 \ldots t_N$.

Output one integer: the minimum number of commands Farmer John needs to use.

【Sample Explanation】 One optimal set of commands Farmer John can use is: ``` Initial temperatures : 1 2 2 2 1 Increase stalls 2..5 by 1 : 1 3 3 3 2 Increase stalls 2..5 by 1 : 1 4 4 4 3 Increase stalls 2..5 by 1 : 1 5 5 5 4 Decrease stalls 3..4 by 1 : 1 5 4 4 4 Decrease stalls 3..4 by 1 : 1 5 3 3 4 ``` 【Constraints】 - Test cases 2-5 satisfy $N \leq 100$. - Test cases 6-8 satisfy $N \leq 1000$. - Test cases 9-10 satisfy $N \leq 100,000$. - In test cases 1-6 and 9, temperature values do not exceed $100$. - In test cases 7-8 and 10, temperature values do not exceed $10,000$. Translated by ChatGPT 5