题目背景
给定一个正整数序列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个中间和,按照从里到外,从左到右的顺序输出。
一道很有价值的区间dp,一共包含了3个子问题;首先用区间dp求出f[i][j]及i-j之间最小的累加和,很显然有:
for(int len = 2; len <= n; ++len) { for(int l = 1; l <= n - len + 1; ++l) { int r = l + len - 1; for(int i = l; i < r; ++i) f[l][r] = min(f[l][r], f[l][i] + f[i + 1][r]); f[l][r] += sum[r] - sum[l - 1]; } }
接着用dfs枚举区间来求出括号的方案,同时求出所有区间的和,用ans作为序号便于输出,这样就A掉了,个别细节需要注意,切切切~~
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 0x3f3f3f3f; const int MAXN = 5e5 + 100; const int MAXM = 3e3 + 10; inline int read() { int x = 0, ff = 1; char ch = getchar(); while(!isdigit(ch)) { if(ch == '-') ff = -1; ch = getchar(); } while(isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } return x * ff; } inline void write(int x) { if(x < 0) putchar('-'), x = -x; if(x > 9) write(x / 10); putchar(x % 10 + '0'); } int n, ans, a[MAXN], sum[MAXN], f[MAXM][MAXM]; priority_queue < pair < int, int > > q; void dfs(int l, int r) { if(l == r) { write(a[l]); return ; } for(int i = r; i >= l; --i) { // 倒序,为了使方案等效时,以括弧靠左为优先~ if(f[l][i] + f[i + 1][r] + sum[r] - sum[l - 1] == f[l][r]) { // 好好思考~ putchar('('); dfs(l, i); putchar('+'); dfs(i + 1, r); putchar(')'); q.push(make_pair(-(++ans), sum[r] - sum[l - 1])); return ; } } } int main() { memset(f, 0x3f, sizeof(f)); n = read(); for(int i = 1; i <= n; ++i) { a[i] = read(); f[i][i] = 0; sum[i] = sum[i - 1] + a[i]; } for(int len = 2; len <= n; ++len) { for(int l = 1; l <= n - len + 1; ++l) { int r = l + len - 1; for(int i = l; i < r; ++i) f[l][r] = min(f[l][r], f[l][i] + f[i + 1][r]); f[l][r] += sum[r] - sum[l - 1]; } } dfs(1, n); putchar('\n'); write(f[1][n]); putchar('\n'); while(!q.empty()) { int x = q.top().second; q.pop(); write(x); putchar(' '); } return 0; }