2021: 添加括号
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：13
解决：7
题目描述
给定一个正整数序列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个中间和，按照从里到外，从左到右的顺序输出。
样例输入 复制
4
4 1 2 3
样例输出 复制
(4+((1+2)+3))
19
3 6 10
提示
注意：输出和的顺序是从左到右，从里到外。还有本题是有多解情况的，在动规寻找分割点时请让分割点尽量靠右（<改成<=）。