国际商业网站,wordpress 友链插件,台州网站设计 解放路,防止域名失效 请牢记题目描述
有一个 n n n 个元素的数组 a a a。不改变序列中每个元素在序列中的位置#xff0c;把它们相加#xff0c;并用括号记每次加法所得的和#xff0c;称为中间和。现在要添上 n − 1 n - 1 n−1 对括号#xff0c;加法运算依括号顺序进行#xff0c;得到 n − …题目描述
有一个 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) ((41)(23))((5)(5))(10)。 有三个中间和是 5 , 5 , 10 5,5,10 5,5,10 它们之和为: 5 5 10 20 5 5 10 20 551020。
第二种添括号方法 ( 4 ( ( 1 2 ) 3 ) ) ( 4 ( ( 3 ) 3 ) ) ( 4 ( 6 ) ) ( 10 ) (4 ((1 2) 3)) (4 ((3) 3)) (4 (6)) (10) (4((12)3))(4((3)3))(4(6))(10)。 有三个中间和是 3 , 6 , 10 3,6,10 3,6,10 它们之和为 3 6 10 19 3 6 10 19 361019 。 输入格式
第一行输入一个整数 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((12)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 k1,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 lr将 l l l 到 r r r 的区间拆分为两个区间进行 dfs l l l 到 l d i , j l d_{i, j} ldi,j l d i , j 1 l d_{i, j} 1 ldi,j1 到 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 in还要输出 。
这样就能轻松地输出算式了。
输出中间和也是同理可用前缀和优化。
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;
}禁止抄袭!!!
