第一行一个正整数n第二行n个用空格分开的正整数a_iai?，表示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,ai?≤300，保证运算过程和结果不超过32位正整数范围。
#include<bits/stdc++.h> using namespace std; const int N = 3e2 + 7; int a[N], dp[N][N], pre[N][N], n, l, r; pair<int, int> q[N]; int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> 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 k = l; k < r; k++) { int c = dp[l][k] + dp[k + 1][r] + (a[l] + a[r]) * a[k]; if (dp[l][r] < c) { dp[l][r] = c; pre[l][r] = k; } } } } cout << dp[1][n] << endl; q[r++] = make_pair(1, n); while (l < r) { pair<int, int> u = q[l++]; int k = pre[u.first][u.second]; cout << k << " "; if (u.first != k) { q[r++] = make_pair(u.first, k); } if (k + 1 != u.second) { q[r++] = make_pair(k + 1, u.second); } } return 0; }
原文：https://www.cnblogs.com/HighLights/p/13328612.html