小笼包
题目背景
JOI同学的午饭,是在中华料理店买的小笼包。这是一种用小麦粉制成的皮包着馅和热汤的料理,吃的时候,热汤会飞溅出来。
题目描述
JOI 同学点的小笼包套餐,由馅料不同的 $N$ 个小笼包组成。$N$ 个小笼包等间隔排成一列,编号为 $1$ 到 $N$。第 $i$ 个小笼包与第 $j$ 个小笼包之间的距离是绝对值 $\vert i - j \vert$。
JOI 同学按照顺序吃小笼包。最初,所有的小笼包的美味度都是 $0$。吃第 $i$ 个小笼包时,汤汁向周围飞散,与第 $i$ 个小笼包距离 $D_i$ 以下的小笼包都淋上了汤汁,而被淋上汤汁的小笼包的美味度会增加 $A_i$。也就是说,吃第 $i$ 个小笼包的时候,第 $j$ 个小笼包 $(1 \leq j \leq N $ 并且 $ i - D_i \leq j \leq i + D_i)$ 还没有吃到的话,第 $j$ 个小笼包的美味度就增加 $A_i$。
![](https://cdn.luogu.com.cn/upload/pic/2340.png)
JOI 同学要在吃小笼包的顺序上下功夫,让吃的小笼包的美味度的合计最大化。
输入输出格式
输入格式
输入共 $3$ 行。
第 $1$ 行是 $1$ 个整数 $N$。
第 $2$ 行是 $N$ 个整数 $D_1,D_2,...,D_N (0 \leq D_i \leq 7) $,以空格分隔。
第 $3$ 行是 $N$ 个整数 $A_1,A_2,...,A_N (0 \leq A_i \leq 1000) $,以空格分隔。
输出格式
共 $1$ 行,输出 JOI 同学吃的小笼包的美味度的合计最大值。
输入输出样例
输入样例 #1
5
1 0 1 1 2
0 2 6 3 4
输出样例 #1
20
输入样例 #2
10
5 2 7 2 6 5 3 5 3 6
8 7 8 4 0 6 0 10 10 0
输出样例 #2
237
说明
样例 $1$ 的说明:以第 $5 \rightarrow$ 第 $3 \rightarrow$ 第 $1 \rightarrow$ 第 $2 \rightarrow$ 第 $4$ 的顺序吃的话,美味度合计为 $20$,因为美味度超过 $20$ 的吃法是不存在的,所以这是最好的。
本题是 2014 年日本信息学奥林匹克(JOI)预选第 6 题。