75 lines
1.7 KiB
C++
75 lines
1.7 KiB
C++
#include <iostream>
|
|
#include <iomanip>
|
|
#include <cstring>
|
|
#include <functional>
|
|
using namespace std;
|
|
|
|
const int N = 105;
|
|
double p[N], q[N];
|
|
double w[N][N], dp[N][N];
|
|
int root[N][N];
|
|
int n;
|
|
|
|
// 输出先序遍历
|
|
void preorder(int l, int r) {
|
|
if (l > r) return;
|
|
int k = root[l][r];
|
|
cout << k;
|
|
// 判断后面是否还有输出
|
|
if (!(l == 1 && r == n))
|
|
cout << " ";
|
|
preorder(l, k - 1);
|
|
preorder(k + 1, r);
|
|
}
|
|
|
|
int main() {
|
|
|
|
cin >> n;
|
|
for (int i = 1; i <= n; i++)
|
|
cin >> p[i];
|
|
for (int i = 0; i <= n; i++)
|
|
cin >> q[i];
|
|
// 初始化空区间
|
|
for (int i = 1; i <= n + 1; i++) {
|
|
dp[i][i - 1] = q[i - 1];
|
|
w[i][i - 1] = q[i - 1];
|
|
}
|
|
|
|
// 区间DP
|
|
for (int len = 1; len <= n; len++) {
|
|
for (int l = 1; l + len - 1 <= n; l++) {
|
|
int r = l + len - 1;
|
|
// 计算 w[l][r]
|
|
w[l][r] = w[l][r - 1] + p[r] + q[r];
|
|
dp[l][r] = 1e18;
|
|
// 枚举根
|
|
for (int k = l; k <= r; k++) {
|
|
double cost =
|
|
dp[l][k - 1]
|
|
+ dp[k + 1][r]
|
|
+ w[l][r];
|
|
// 字典序最小：相等时取更小根
|
|
if (cost < dp[l][r]) {
|
|
dp[l][r] = cost;
|
|
root[l][r] = k;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// 输出先序遍历
|
|
bool first = true;
|
|
|
|
function<void(int,int)> dfs = [&](int l, int r) {
|
|
if (l > r) return;
|
|
int k = root[l][r];
|
|
if (!first) cout << " ";
|
|
first = false;
|
|
cout << k;
|
|
dfs(l, k - 1);
|
|
dfs(k + 1, r);
|
|
};
|
|
|
|
dfs(1, n);
|
|
return 0;
|
|
} |