题目描述
有一个 n n n 个元素的数组 a a a。不改变序列中每个元素在序列中的位置，把它们相加，并用括号记每次加法所得的和，称为中间和。现在要添上 n − 1 n - 1 n−1 对括号，加法运算依括号顺序进行，得到 n − 1 n - 1 n−1 个中间和，求出使中间和之和最小的添括号方法。
例如：给出序列是 4 , 1 , 2 , 3 4,1,2,3 4,1,2,3 。
第一种添括号方法：
( ( 4 + 1 ) + ( 2 + 3 ) ) = ( ( 5 ) + ( 5 ) ) = ( 10 ) ((4 + 1) + (2 +3)) = ((5) + (5)) = (10) ((4+1)+(2+3))=((5)+(5))=(10)。
有三个中间和是 5 , 5 , 10 5,5,10 5,5,10 ，它们之和为: 5 + 5 + 10 = 20 5 + 5 + 10 = 20 5+5+10=20。
第二种添括号方法：
( 4 + ( ( 1 + 2 ) + 3 ) ) = ( 4 + ( ( 3 ) + 3 ) ) = ( 4 + ( 6 ) ) = ( 10 ) (4 + ((1 + 2) + 3)) = (4 + ((3) + 3)) = (4 + (6)) = (10) (4+((1+2)+3))=(4+((3)+3))=(4+(6))=(10)。
有三个中间和是 3 , 6 , 10 3,6,10 3,6,10 ，它们之和为 3 + 6 + 10 = 19 3 + 6 + 10 = 19 3+6+10=19 。
输入格式
第一行输入一个整数 n n n，表示 a a a 元素个数。
第二行输入 n n n 个整数 a i a_i ai。
输出格式
第一行输出添加括号的方法。
第二行输出最终的中间和之和。
第三行输出 n − 1 n - 1 n−1 个中间和，按照从里到外，从左到右的顺序输出。
样例
样例输入1：
4
4 1 2 3
样例输出1：
(4+((1+2)+3))
19
3 6 10
样例解释见上。
数据范围
1 ≤ n ≤ 20 1 \le n \le 20 1≤n≤20
1 ≤ a i ≤ 100 1 \le a_i \le 100 1≤ai≤100
题解
将 + + + 看成合并左右两个元素， ( ) () () 限定合并顺序。
按照正常的 区间dp ，很容易计算出中间和之和。
那如何输出算式和每个中间和呢?
当把区间 i , k i, k i,k 和 k + 1 , j k + 1, j k+1,j 合并成 i , j i, j i,j 时，记录 k − i k - i k−i 的值（合并位置 d i , j d_{i, j} di,j）。
然后写一个 dfs，传两个参数 l l l 和 r r r，表示 l l l 到 r r r 的区间。
- 如果 l ≥ r l \ge r l≥r，返回。
- 如果 l < r l < r l<r，将 l l l 到 r r r 的区间拆分为两个区间进行
dfs（ l l l 到 l + d i , j l + d_{i, j} l+di,j， l + d i , j + 1 l + d_{i, j} + 1 l+di,j+1 到 r r r），并将 l l l 的左括号数（ f 1 l f1_l f1l）加 1 1 1， r r r 的右括号数（ f 2 r f2_r f2r）加 1 1 1。
接下来从 1 1 1 到 n n n 输出，先输出 f 1 i f1_i f1i 个左括号，再输出 a i a_i ai，然后输出 f 2 i f2_i f2i 个右括号。如果 i ≠ n i \ne n i=n，还要输出 + + +。
这样就能轻松地输出算式了。
输出中间和也是同理，可用前缀和优化。
int f[40][40];//dp
int sum[40];//前缀和
int d[40][40];//从 i 到 j 合并的点
int f1[40], f2[40];//左括号数和右括号数
//算式
void dfs(int x, int y){
if(x >= y){
return;
}
dfs(x, x + d[x][y]);
dfs(x + d[x][y] + 1, y);
f1[x] ++;
f2[y] ++;
}
//中间和
void dfs2(int x, int y){
if(x >= y){
return;
}
dfs2(x, x + d[x][y]);
dfs2(x + d[x][y] + 1, y);
printf("%d ", sum[y] - sum[x - 1]);
}
int main(){
输入
//初始化
memset(f, 0x3f, sizeof(f)))；
memset(d, 0, sizeof(d));
for(int i = 1; i <= n; ++ i){
f[i][i] = 0;
}
//前缀和
for(int i = 1; i <= n; ++ i){
sum[i] = sum[i - 1] + a[i];
}
for(int k = 1; k < n; ++ k){
for(int i = 1; i <= n - k; ++ i){
int j = i + k;
for(int u = i; u < j; ++ u){
//更新 f[i][j]
if(f[i][j] > f[i][u] + f[u + 1][j]){
f[i][j] = f[i][u] + f[u + 1][j];
d[i][j] = u - i;
}
}
f[i][j] += sum[j] - sum[i - 1];
}
}
//输出
dfs(1, n);
for(int i = 1; i <= n; ++ i){
while(f1[i]）{
putchar('(');
f1[i] --;
}
printf("%d", a[i]);
while(f2[i]){
putchar(')');
f2[i] --;
}
if(i != n){
putchar('+');
}
}
printf("\n%d\n", f[1][n]);
dfs2(1, n)；
return 0;
}
禁止抄袭!!!