爬楼梯

爬楼梯

题目描述

b6e0看见了一段楼梯。这段楼梯有\(n\)阶,他现在在第\(0\)阶,他想要到第\(n\)阶。
对于所有\(i\)(\(1\le i\le n\)),可以从第\(a_i\)阶~第\(i-1\)阶直接跨到第\(i\)阶。每一阶还有一个值\(b_i\),表示从\(j\)到\(i\)(\(j<i\))花费\(b_j+b_i\)的体力。特殊地,\(b_0=0\)。
b6e0想知道他到达第\(n\)阶花费的最少体力是多少。

输入格式

第一行输入整数\(n\),表示这段楼梯有\(n\)阶。
第二行输入\(n\)个整数,第\(i\)个数表示\(a_i\)。
第三行输入\(n\)个整数,第\(i\)个数表示\(b_i\)。
输入保证正确,不用判错。

输出格式

输出到达第\(n\)阶花费的最少体力。

输入输出样例1

输入

5
0 1 2 3 4
1 2 3 4 5

输出

25

输入输出样例2

输入

10
0 0 2 3 1 4 6 6 6 1
100000 5 4 3 2 1 99 98 100 10000

输出

10010

样例解释

对于样例一,唯一的一条路线是\(0\)->\(1\)->\(2\)->\(3\)->\(4\)->\(5\),花费为\(1+(1+2)+(2+3)+(3+4)+(4+5)=25\)。

数据范围

对于100%的数据,\(1\le n\le5\times10^5\)。对于所有\(i\)(\(1\le i\le n\)),\(0\le a_i<i\),\(-10^9\le b_i\le10^9\)。
Subtask 1(15pts): \(n\le10\)。
Subtask 2(25pts): \(n\le1000\)。
Subtask 3(10pts): 对于所有\(i\)(\(2\le i\le n\)),\(b_{i-1}\le b_i\)。
Subtask 4(10pts): 对于所有\(i\)(\(2\le i\le n\)),\(a_{i-1}\le a_i\)。
Subtask 5(10pts): 对于所有\(i\)(\(1\le i\le n\)),\(1\le b_i\le10^9\)。
Subtask 6(30pts): 无特殊限制。

贡献者

题面,数据:b6e0
核题:Ducati、关怀大佬

信息

ID
1013
难度
5
分类
(无)
标签
递交数
2
已通过
1
通过率
50%
被复制
1
上传者