2395: 走走跳跳
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：18
解决：7
题目描述
有 n 个位置排成一排，第 i 个位置都有一个分数 ai（分数可能是正数，也可能是负数）。小爱从 1 号位置出发，最终要走到 n 号位置。当小爱在第 i 个位置时，有两种选择：
- 她可以直接走到下一个位置（也就是 i+1 号位置）；
- 也可以选择跳到第 ti 号位置（保证i<ti）。
输入
第一行：一个整数 n；
第二行：n 个整数，表示 a1,a2,⋯,an；
第三行：n−1个整数，表示 t1,t2,⋯,tn−1；
第二行：n 个整数，表示 a1,a2,⋯,an；
第三行：n−1个整数，表示 t1,t2,⋯,tn−1；
输出
单个整数：表示可能拿到的最高分数
样例输入 复制
3
4 -2 6
3 3样例输出 复制
10提示
数据范围：
对于 30% 的数据，保证 1≤n≤50；
对于 60% 的数据，保证 1≤n≤5000；
对于 100% 的数据，保证 1≤n≤100,000；
−107≤ai≤107；
i<ti≤n；
对于 30% 的数据，保证 1≤n≤50；
对于 60% 的数据，保证 1≤n≤5000；
对于 100% 的数据，保证 1≤n≤100,000；
−107≤ai≤107；
i<ti≤n；