/ Vijos / 题库 /

添加括号

添加括号

背景

给定一个正整数序列a(1),a(2),...,a(n),(1<=n<=20)
不改变序列中每个元素在序列中的位置,把它们相加,并用括号记每次加法所得的和,称为中间和。

例如:
给出序列是4,1,2,3。

第一种添括号方法:
((4+1)+(2+3))=((5)+(5))=(10)
有三个中间和是5,5,10,它们之和为:5+5+10=20
第二种添括号方法

(4+((1+2)+3))=(4+((3)+3))=(4+(6))=(10)
中间和是3,6,10,它们之和为19。

描述

现在要添上n-1对括号,加法运算依括号顺序进行,得到n-1个中间和,求出使中间和之和最小的添括号方法。如果有多组最优解,考虑将括号尽可能往前放。

格式

输入格式

共两行。

第一行,为整数n。(1<=n<=20)
第二行,为a(1),a(2),...,a(n)这n个正整数,每个数字不超过100。

输出格式

输出3行。

第一行,为添加括号的方法。

第二行,为最终的中间和之和。

第三行,为n-1个中间和,按照从左到右,从里到外的顺序输出。

样例1

样例输入1

4
4 1 2 3

样例输出1

(4+((1+2)+3))
19
3 6 10

限制

各个测试点1s

来源

MaoLaoda

信息

ID
1038
难度
5
分类
动态规划 点击显示
标签
(无)
递交数
2553
已通过
946
通过率
37%
上传者

相关