3230 - 分离与合体

一开始LYD可以选择从1~n-1的任何一个区域(记为K)进入,进入后LYD会在K区域发生分离,从而分离为两个小LYD。分离完成的同时会有一面墙在k和k+1区域之间升起,从而把1~k和k+1~n,并在各自的区间内任选除了区间末尾区域以外(即1~k-1或k+1~n-1)的任何一个区域再次发生分离,就一共有了4个小小的LYD……重复进行以上所叙述的分离,直到每个小LYD发现自己所在的区间只剩下了一个区域,他们就可以抱起自己梦寐以求的OI金钥匙。

但是LYD不能就这么分成n多个个体存在于世界上,这些小LYD还会再合体,合体的两个小LYD所在的区间中间的墙会消失。合体会获得一定的价值,计算方法是:(合并后所在区间的左右端区域里金钥匙的价值之和)乘(之前分离的时候所在区域的金钥匙价值)。

例如,LYD曾经在1~3区间中的2号区域分离成为1~2和3两个区间,合并时获得的价值就是:(1号金钥匙价值+3号价值)*(2号金钥匙价值)。

LYD请你编程求出最终可以获得的总价值最大是多少。并按照分离阶段从前到后,区域从左到右的顺序,输出发生分离的区域编号。

例如,先打印1分为2的分离区域,然后从左到右打印2分为4的分离区域,然后是4分8的……

注意:若有多种方案,选择分离区域尽量靠左的方案(也可以理解为输出字典序最小的)。

输入

第一行一个正整数n(2≤n≤300)

第二行为n个空格分开的正整数,表示1~n区域里每把金钥匙的价值。

保证运算过程及结果不超出int范围。

输出

第一行一个数,即获得的最大价值。

第二行按照分离阶段从前到后,区域从左到右的顺序,输出发生分离的区域编号,中间用一个空格隔开,若有多种方案,选择分离区域尽量靠左的方案(也可以理解为输出字典序最小的)。

样例

输入

71 2 3 4 5 6 7

输出

2381 2 3 4 5 6

提示

【数据规模】

对于100%的数据,N≤300,a[i]≤300。

对于20%的数据,N≤10。

对于40%的数据,N≤50。

来源

动规专题

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题