背景 Background
给定一个正整数序列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。
描述 Description
现在要添上n-1对括号，加法运算依括号顺序进行，得到n-1个中间和，求出使中间和之和最小的添括号方法。
输入格式 Input Format
共两行。
第一行，为整数n。(1<=n<=20)
第二行，为a(1),a(2),...,a(n)这n个正整数，每个数字不超过100。
输出格式 Output Format
输出3行。
第一行，为添加括号的方法。
第二行，为最终的中间和之和。
第三行，为n-1个中间和，按照从里到外，从左到右的顺序输出。
样例输入 Sample Input
4
4 1 2 3
样例输出 Sample Output
(4+((1+2)+3))
19
3 6 10
【参考程序】：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int a[50],sum[50],F[100][100],cut[100][100];
int n;
void cout2(int i,int j)
{
if (i>=j) return ;
cout2(i,cut[i][j]);
cout2(cut[i][j]+1,j);
printf("%d ",sum[j]-sum[i-1]);
}
void cout1(int i,int j)
{
if (i>=j)
{
printf("%d",a[i]); return ;
}
printf("("); cout1(i,cut[i][j]);
printf("+"); cout1(cut[i][j]+1,j);
printf(")");
}
int main()
{
scanf("%d",&n);
sum[0]=0;
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
F[i][i]=0; cut[i][i]=i;
}
int j,p,Min;
for (int len=2;len<=n;len++)
for (int i=1;i<=n-len+1;i++)
{
j=i+len-1; Min=0xFFFFFFF;
for (int k=i;k<=j-1;k++)
if (F[i][k]+F[k+1][j]<=Min)
{
Min=F[i][k]+F[k+1][j];
p=k;
}
cut[i][j]=p;
F[i][j]=Min+sum[j]-sum[i-1];
}
cout1(1,n);
printf("\n%d\n",F[1][n]);
cout2(1,n); printf("\n");
return 0;
}