海口建设网站的公司/电商广告网络推广

题目背景

给定一个正整数序列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; 
}