经过在机房里数日的切磋,LYD 从杜神牛那里学会了分离与合体,出关前,杜神牛给了他一个测试……
杜神牛造了 $n$ 个区域,他们紧邻着排成一行,编号 $1..n$。在每个区域里都放着一把 OI 界的金钥匙,每一把都有一定的价值,LYD 当然想得到他们了。然而杜神牛规定 LYD 不能一下子把他们全部拿走,而是每次只可以拿一把。为了尽快得到所有金钥匙,LYD 自然就用上了刚学的分离与合体特技。
一开始 LYD 可以选择 $1..n-1$ 中的任何一个区域进入,我们不妨把这个区域记为 $k$。进入后 LYD 会在 $k$ 区域发生分离,从而分离成两个小 LYD。分离完成的同时会有一面墙在 $k$ 区域和 $k+1$ 区域间升起,从而把 $1..k$ 和 $k+1..n$ 阻断成两个独立的区间,并在各自区间内任选除区间末尾之外(即从 $1..k-1$ 和 $k+1..n-1$中选取)的任意一个区域再次发生分离,这样就有了四个小小 LYD……重复以上所叙述的分离,直到每个小 LYD 发现自己所在的区间只剩下了一个区域,那么他们就可以抱起自己梦寐以求的 OI 金钥匙。
但是 LYD 不能就分成这么多个个体存在于世界上,这些小 LYD 还会再合体,合体的小 LYD 所在区间中间的墙会消失。合体会获得 ((合并后所在区间左右端区域里金钥匙价值之和)×(之前分离的时候所在区域的金钥匙价值))。
例如,LYD 曾在 $1..3$ 区间中的 $2$ 号区域分离成为 $1..2$ 和 $3..3$ 两个区间,合并时获得的价值就是 (( $1$ 号金钥匙价值 $+ 3$ 号金钥匙价值)×( $2$ 号金钥匙价值))。
LYD 请你编程求出最终可以获得的最大总价值,并按照分离阶段从前到后,区域从左到右的顺序,输出发生分离区域编号。若有多种方案,选择分离区域尽量靠左的方案(也可以理解为输出字典序最小的)。
例如先打印一分为二的区域,然后从左到右打印二分为四的分离区域,然后是四分为八的……
【输入】
第一行一个正整数 $n$
第二行 $n$ 个用空格分开的正整数 $a_i$ ,表示 $1..n$ 区域里每把金钥匙的价值。
【输出】
第一行一个数,表示获得的最大价值
第二行按照分离阶段从前到后,区域从左到右的顺序,输出发生分离区域编号。若有多种方案,选择分离区域尽量靠左的方案(也可以理解为输出字典序最小的)。
【输入样例】
7 1 2 3 4 5 6 7
【输出样例】
238 1 2 3 4 5 6
【提示】
数据范围与提示:
对于 20% 的数据,$n≤10$;
对于 40% 的数据,$n≤50$;
对于 100% 的数据,$n,a_i≤300$,保证运算过程和结果不超过 $32$ 位正整数范围。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <queue> 5 6 using namespace std; 7 8 const int N = 400; 9 int f[N][N], g[N][N]; 10 int n; 11 int w[N]; 12 int sum[N]; 13 int get(int l, int r) 14 { 15 return sum[r] - sum[l - 1]; 16 } 17 18 int main() 19 { 20 scanf("%d", &n); 21 for (int i = 1; i <= n; i++) 22 { 23 scanf("%d", &w[i]); 24 } 25 26 for (int len = 2; len <= n; len++) 27 { 28 for (int l = 1; l + len - 1 <= n; l++) 29 { 30 int r = l + len - 1; 31 if (l == r) 32 f[l][r] = w[l]; 33 for (int k = l; k < r; k++) 34 { 35 36 int t = f[l][k] + f[k + 1][r] + (w[l] + w[r]) * w[k]; 37 38 if (t > f[l][r]) 39 f[l][r] = t,g[l][r] = k; 40 } 41 } 42 } 43 printf("%d\n", f[1][n]); 44 45 queue<pair<int, int> > q; 46 q.push(make_pair(1, n)); 47 while (q.size()) 48 { 49 int l = q.front().first; 50 int r = q.front().second; 51 q.pop(); 52 if (l != r) 53 { 54 printf("%d ", g[l][r]); 55 q.push(make_pair(l, g[l][r])); 56 q.push(make_pair(g[l][r] + 1, r)); 57 } 58 } 59 return 0; 60 }