#470. 分离与合体

分离与合体

题目描述

经过在机房里数日的切磋,LYD 从杜神牛那里学会了分离与合体,出关前,杜神牛给了他一个测试……

杜神牛造了 n\red{n} 个区域,他们紧邻着排成一行,编号1..n\red{ 1..n}。在每个区域里都放着一把 OI 界的金钥匙,每一把都有一定的价值,LYD 当然想得到他们了。然而杜神牛规定 LYD 不能一下子把他们全部拿走,而是每次只可以拿一把。为了尽快得到所有金钥匙,LYD 自然就用上了刚学的分离与合体特技。

一开始 LYD 可以选择 1..n1\red{1..n-1} 中的任何一个区域进入,我们不妨把这个区域记为 k\red{k}。进入后 LYD 会在k\red{ k} 区域发生分离,从而分离成两个小 LYD。分离完成的同时会有一面墙在 k\red{k} 区域和 k+1\red{k+1} 区域间升起,从而把 1..k\red{1..k}k+1..n\red{k+1..n }阻断成两个独立的区间,并在各自区间内任选除区间末尾之外(即从 1..k1\red{1..k-1}k+1..n1\red{ k+1..n-1}中选取)的任意一个区域再次发生分离,这样就有了四个小小 LYD……重复以上所叙述的分离,直到每个小 LYD 发现自己所在的区间只剩下了一个区域,那么他们就可以抱起自己梦寐以求的 OI 金钥匙。

但是 LYD 不能就分成这么多个个体存在于世界上,这些小 LYD 还会再合体,合体的小 LYD 所在区间中间的墙会消失。合体会获得 ((合并后所在区间左右端区域里金钥匙价值之和)×\red{×}(之前分离的时候所在区域的金钥匙价值))。

例如,LYD 曾在 1..3\red{1..3}区间中的 2 号区域分离成为1..2\red{ 1..2 }3..3\red{3..3 }两个区间,合并时获得的价值就是 (( 1\red{1} 号金钥匙价值 +3\red{+ 3} 号金钥匙价值)×\red{×}( 2\red{2} 号金钥匙价值))。

LYD 请你编程求出最终可以获得的最大总价值,并按照分离阶段从前到后,区域从左到右的顺序,输出发生分离区域编号。若有多种方案,选择分离区域尽量靠左的方案(也可以理解为输出字典序最小的)。

例如先打印一分为二的区域,然后从左到右打印二分为四的分离区域,然后是四分为八的……

输入格式

第一行一个正整数n\red{ n} 第二行n\red{ n} 个用空格分开的正整数 ai\red{a_i}​ ,表示1..n\red{ 1..n }区域里每把金钥匙的价值。

输出格式

第一行一个数,表示获得的最大价值

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

样例

输入样例

7
1 2 3 4 5 6 7

输出样例

238
1 2 3 4 5 6

提示

对于20%\red{ 20\%} 的数据,n10\red{n\le 10}

对于40%\red{ 40\% }的数据,n50\red{n\le 50}

对于 100%\red{100\%} 的数据,n,ai300\red{n,a_i\le 300},保证运算过程和结果不超过 32\red{32} 位正整数范围。

统计

相关

在以下作业中:

DP