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