加分二叉树(记忆化搜索)

题目：

一棵二叉树的中序遍历是1、2、3...n。每个结点有点权a[i]。让你确定一棵树使val最大。最后输出val并给出先序遍历序列。
（n最大100）

做法：

一个区间DP的题。但感觉dfs码起来更清晰，思路是一样的。
对[l,r]区间确定的一棵二叉树，它的我们通过枚举根节点的位置来转移： 转移时记录此区间的根，回头打印先序遍历时就很简单了。
具体细节看代码咯。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 110;
int n, a[N], dp[N][N], path[N][N];
int dfs(int l, int r){
    if (dp[l][r] != -1) return dp[l][r];
    if (l == r){
        path[l][r] = l;
        return a[l];
    }
    if (l > r) return 1;
    int& ans = dp[l][r] = 0;
    for (int i = l; i <= r; ++i){
        int tmp = dfs(l, i-1)*dfs(i+1, r)+a[i];
        if (ans < tmp){
            ans = tmp;
            path[l][r] = i;
        }
    }
    return ans;
}
void getpath(int l, int r){
    if (l > r) return;
    cout << path[l][r] << ' ';
    getpath(l, path[l][r]-1);
    getpath(path[l][r]+1, r);
}
int main(void){ 
    IOS;
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    memset(dp, -1, sizeof dp);
    cout << dfs(1, n) << endl;
    getpath(1, n);
    return 0;
}