Air Cownditioning

题目描述

农夫约翰的牛群 $N$ 对牛棚里的室温非常挑剔。有些奶牛喜欢偏凉的温度，而另一些则更喜欢温暖一些。

农夫约翰的牛棚包含一排连续的 $N$ 个牛栏，编号为 $1 \ldots N$，每个牛栏里都有一头奶牛。第 $i$ 头奶牛希望她所在牛栏的温度为 $p_i$，而目前该牛栏的温度为 $t_i$。为了确保每头奶牛都感到舒适，农夫约翰安装了一套新的空调系统，其控制方式有些特别。他可以向系统发送指令，使一段连续牛栏的温度升高或降低 1 个单位——例如“将牛栏 $5 \ldots 8$ 的温度升高 1 个单位”。这段牛栏的长度可以短至仅包含一个牛栏。

请帮助农夫约翰确定，为了让每个牛栏的温度都达到其奶牛的理想温度，他最少需要发送多少条指令。

输入格式

第一行输入包含 $N$。 第二行包含 $N$ 个非负整数 $p_1 \ldots p_N$，以空格分隔。 最后一行包含 $N$ 个非负整数 $t_1 \ldots t_N$。

输出格式

请输出一个整数，表示农夫约翰最少需要使用的指令条数。

5
1 5 3 3 4
1 2 2 2 1

5

提示

农夫约翰可使用的一组最优指令如下： 初始温度：1 2 2 2 1 提高牛栏 2..5：1 3 3 3 2 提高牛栏 2..5：1 4 4 4 3 提高牛栏 2..5：1 5 5 5 4 降低牛栏 3..4：1 5 4 4 4 降低牛栏 3..4：1 5 3 3 4

评分： 测试点 2-5 满足 $N \leq 100$。 测试点 6-8 满足 $N \leq 1000$。 测试点 9-10 满足 $N \leq 100,000$。 在测试点 1-6 和 9 中，温度值不超过 $100$。 在测试点 7-8 和 10 中，温度值不超过 $10,000$。 题目来源：Brian Dean

标签: USACO|2021|Bronze

来源

USACO|2021|Bronze