4.山
题目描述
XZH 非常喜欢山。
身为美术学校毕业的 XZH 对山的形状有一定的要求。他希望对于 i∈[2,n],第 i 座山比第 i−1 座山恰好高 ai 的高度。
每座山有初始高度,第 i 座山的初始高度为 hi 。
同时,他可以使用“膜法”来让一座山的高度 hi 变为他想要的任意高度,但这一操作会消耗 XZH 1 元。
考虑到山必定是一个有高度的实体,不能直接把它夷为平地或者变成一个坑,所以他的功能有一定的限制,改变之后,山的高度需要满足 hi ≥1。
求 XZH 花费的最小值,让山达到他的审美。
输入格式第一行输出一个整数 id,表示数据组,帮助大家取得部分分。(其中,样例的 id 设为 0)。
第二行输入一个整数 T。
对于每一组数据:第一行输入一个整数 n。
第二行输入 n 个整数,第 i 个整数表示第 i 座山的高度 hi 。
第三行输入 n−1 个数,第 i 个数表示 XZH 希望第 i 座山比第 i+1 座山矮 ai 。
输出格式一行,一个整数,表示 XZH 的最小花费。
样例
样例输入 1 样例输出 1
0
2
5
1 2 5 3 2
1 1 0 -1
7
1 9 1 9 8 1 1
1 1 4 5 1 4 1
6
样例说明
样例 1 解释:对于第一组样例,一种可行的实现是,把 h3 改成 3 即可。
对于第二组样例,一组可行的实现是,将数列 h 改为 {1,2,3,7,12,13,17},可能有多组解,但是可以证明没有任意一组解比样例给出的值更小。
提示
id 特殊性质 数据占比
1 n=2 10%
2 1≤n≤1000 30%
3 hi =1,ai ≥0 15%
4 ai =0 15%
5 无 30%
对于 100% 的数据 1≤n≤105,−10≤ai ≤10,1≤hi ≤106,1≤T≤6。
给个C++源码吧