给定一个正整数序列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个中间和，求出使中间和之和最小的添括号方法。
思路：
区间dp
f[i][j]表示区间[i,j]和并后的最小和
然后因为这题还有一个毒瘤输出
所以还要有一个附加数组pos，记k=pos[i][j]，pos[i][j]表示区间[i,j]合并时是由[l,k]和[k+1,j]两个区间合并的，然后用一个递归就可以输出结果。
CODE：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 #define MAXN 1010 7 int nums[MAXN],sum[MAXN]; 8 int f[MAXN][MAXN],pos[MAXN][MAXN]; 9 int i,j,k,m,n,ans; 10 void print(int l,int r){ 11 if(l==r){ 12 printf("%d",nums[l]); 13 return; 14 } 15 int mid=pos[l][r]; 16 putchar(‘(‘); 17 print(l,mid); 18 putchar(‘+‘); 19 print(mid+1,r); 20 putchar(‘)‘); 21 } 22 void print2(int l,int r){ 23 if(l==r) return; 24 int mid=pos[l][r]; 25 print2(l,mid); 26 print2(mid+1,r); 27 printf("%d ",sum[r]-sum[l-1]); 28 } 29 int main(){ 30 scanf("%d",&n); 31 for(i=1;i<=n;i++){ 32 scanf("%d",nums+i); 33 nums[n+i]=nums[i]; 34 } 35 sum[0]=0; 36 for(i=1;i<=n;i++) sum[i]=sum[i-1]+nums[i]; 37 for(i=2;i<=n;i++){ 38 for(j=1;j<=n-i+1;j++){ 39 int t=i+j-1; 40 f[j][t]=1000000000; 41 for(k=j;k<=t-1;k++){ 42 if(f[j][t]>=f[j][k]+f[k+1][t]){ 43 f[j][t]=f[j][k]+f[k+1][t]; 44 pos[j][t]=k; 45 } 46 } 47 f[j][t]+=sum[t]-sum[j-1]; 48 } 49 } 50 ans=f[1][n]; 51 print(1,n); printf("\n"); 52 printf("%d\n",ans); 53 print2(1,n); printf("\n"); 54 return 0; 55 }
原文：https://www.cnblogs.com/linxif2008/p/9900362.html