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

题目

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;
}