生命仪式-j9国际集团直营

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级新生赛

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