题目

P1040 [NOIP 2003 提高组] 加分二叉树

算法标签: 区间$dp$, 动态规划, $dfs$

思路

给出的是一颗子树的中序遍历, $score=l\times r+root$, 如果当前根节点的某个子树为空, 将其视为$1$, 求最大的分数, 自然而然的想到将每个子树按照根节点的选择进行划分, 因为中序遍历是左根右,. 因此可以枚举每个子树的根节点的选取情况, 定义状态表示$f[i][j]$为中序遍历为$i$到$j$的子树的最大加分, 那么$f[1][n]$就是答案

代码

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;typedef long long LL;
const int N = 40;int n, w[N];
int fa[N][N];
LL f[N][N];void dfs(int l, int r) {int k = fa[l][r];if (k == 0) return;cout << k << " ";dfs(l, k - 1), dfs(k + 1, r);
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= n; ++i) cin >> w[i];for (int i = 1; i <= n; ++i) f[i][i] = w[i], fa[i][i] = i;for (int len = 2; len <= n; ++len) {for (int i = 1; i + len - 1 <= n; ++i) {int j = i + len - 1;//枚举根节点for (int k = i; k <= j; ++k) {int l_val = k == i ? 1 : f[i][k - 1];int r_val = k == j ? 1 : f[k + 1][j];LL curr = (LL) l_val * r_val + w[k];if (curr > f[i][j]) {f[i][j] = curr;fa[i][j] = k;}}}}cout << f[1][n] << "\n";dfs(1, n);return 0;
}