问题 4804 --空调系统

4804: 空调系统★★

时间限制: 1 Sec  内存限制: 128 MB
提交: 48  解决: 25
[提交][状态][命题人:]

题目描述

John 的 N 头奶牛对他们牛棚的室温非常挑剔。有些奶牛喜欢温度低一些,而有些奶牛则喜欢温度高一些。

John 的牛棚包含一排 N 个牛栏,编号为 1…N,每个牛栏里有一头牛。 第i头奶牛希望她的牛栏中的温度是pi,而现在她的牛栏中的温度是ti。为了确保每头奶牛都感到舒适,John 安装了一个新的空调系统。该系统进行控制的方式非常有趣,他可以向系统发送命令,告诉它将一组连续的牛栏内的温度升高或降低 1 个单位——例如「将牛栏 5…8的温度升高 1 个单位」。一组连续的牛栏最短可以仅包含一个牛栏。

请帮助 John 求出他需要向新的空调系统发送的命令的最小数量,使得每头奶牛的牛栏都处于其中的奶牛的理想温度。

输入

输入的第一行包含 N。下一行包含 N 个非负整数 p1…pN,用空格分隔。最后一行包含 N个非负整数 t1…tN

输出

输出一个整数,为 John 需要使用的最小指令数量。
样例输入
Copy
5
1 5 3 3 4
1 2 2 2 1
样例输出
Copy
5

提示

一组最优的John 可以使用的指令如下:

初始温度     :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≤100。
  • 测试点 6-8 满足 N≤1000。
  • 测试点 9-10 满足 N≤100,000。
  • 测试点 1-6 和 9 中,温度值不超过 100。
  • 测试点 7-8 和 10 中,温度值不超过 10,000。

来源

 

[提交][状态]