← 返回题目

题库练习小笼包

← 上一题下一题 →

A2144 | $小笼包$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

JOI同学点的小笼包套餐，由馅料不同的N个小笼包组成。 N个小笼包等间隔排成一列，编号为1到N。第i个小笼包与第j个小笼包之间的距离是绝对值| i - j |。 JOI同学按照顺序吃小笼包。最初，所有的小笼包的美味度都是0。吃第i个小笼包时，汤汁向周围飞散，与第i个小笼包距离Di以下的小笼包都淋上了汤汁，而被淋上汤汁的小笼包的美味度会增加Ai。也就是说，吃第i个小笼包的时候，第j个小笼包 (1 ≦ j ≦ N 且 i - Di ≦ j ≦ i + Di)还没有吃到的话，第j个小笼包的美味度就增加Ai。![](/uploads/acgo/image/c08a009d7e7481f2_02b75d8ce96d.png) JOI 同学要在吃小笼包的顺序上下功夫，让吃的小笼包的美味度的合计最大化。

输入格式

输入共3行。 第1行是1个整数N。 第2行是N个整数D1, D2, ..., DN (0 ≦ Di ≦ 7) ，以空格分隔。 第3行是N个整数A1, A2, ..., AN (0 ≦ Ai ≦ 1000)，以空格分隔。

输出格式

共1行，输出JOI同学吃的小笼包的美味度的合计最大值。

输入输出样例

输入 #1

5
1 0 1 1 2
0 2 6 3 4

输出 #1

输入 #2

10
5 2 7 2 6 5 3 5 3 6
8 7 8 4 0 6 0 10 10 0

输出 #2

C++ 编辑器

输入

输出