洛谷题单指南-树与图上的动态规划-P1040 [NOIP 2003 提高组] 加分二叉树

原题链接：https://www.luogu.com.cn/problem/P1040

题意解读：计算最高加分，以及前序遍历。

解题思路：用递归+记忆化搜索比较直观，关键点是如何记录方案

设f[i][j]表示从i到j的最大加分值，用于记忆化搜索，
设g[i][j]记录最大加分值的分割点，也就是树的根节点，用于记录方案，
设dfs(l,r)表示中序l~r之间的最大加分值，对于一个区间l~r，枚举中点，递归计算最大加分值，同步更新g[l][r]的位置即可。
输出前序遍历时，只要递归输出区间的中点、也就是根节点，即是前序遍历。
100分代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 35;

int a[N];
int f[N][N]; // f[i][j]表示从i到j的最大加分值
int g[N][N]; // g[i][j]记录最大加分值的分割点，也就是树的根节点
int n, ans;

int dfs(int l, int r)
{    
    if(f[l][r]) return f[l][r]; //如果已经计算过，直接返回
    if(l > r) return 1;
    if(l == r)  
    {
        g[l][r] = l;
        return f[l][r] = a[l];
    }

    int maxv = 0;
    for(int i = l; i <= r; i++)
    {
        int lres = dfs(l, i - 1);
        int rres = dfs(i + 1, r);
        int res = lres * rres + a[i];
        if(res > maxv)
        {
            maxv = res;
            g[l][r] = i; //记录最大值的分割点
        }
    }

    return f[l][r] = maxv;
}

void show(int l, int r)
{
    if(l > r) return;
    cout << g[l][r] << " ";
    if(l < r)
    {
        show(l, g[l][r] - 1);
        show(g[l][r] + 1, r);
    }
}

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    ans = dfs(1, n);
    cout << ans << endl;
    show(1, n);
    return 0;
}