问题 1326. -- 生命仪式

1326: 生命仪式

时间限制:5000 ms 内存限制:128 MB
提交:34 解决:12
[ 提交][ 状态][ 讨论版]

题目描述

tsy的另一个身份是一位mo法师，他准备进行一个生命延续的仪式（为一位长者），仪式的规则是这样的，N个人围成一圈（N号与1号相邻，其余依次相邻），每个人有一个能量值ai，每次选取圈内的一个人进行献祭，这个人立刻退（ren）出（jian）仪（zheng）式（fa），而长者则得到一些时间，时间的大小为选取人选和当前左右两人的能量之积（左右两人在还剩两人时是重复的），最后还剩一人时仪式结束，现在问你怎样操作这个仪式可以使得长者得到的时间总量最大。

输入

多组数据

每组第一行一个数字N代表人数(2 <= N <= 400)

之后N个数字ai代表第i人的能量值(ai <= 150)

输出

一行一个数字，代表得到的最大时间

样例输入

2 4 2

样例输出

32

提示

这不是贪心

来源

软院科协2017级新生赛

[ 提交][ 状态][ 讨论版]
Baidu
map