加分二叉树

加分二叉树 树型区间dp

设一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出；（1）tree的最高加分（2）tree的前序遍历

感觉自己宛如一个智障。。这道题就是个区间dp，没什么好说的。复杂度是(O(n^3))？用的是记忆化搜索。

#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn=35;
int n, score[maxn];
int f[maxn][maxn], root[maxn][maxn];

void dfs(int l, int r){
    if (l>r) return;
    if (f[l][r]!=1) return;
    if (l==r){ f[l][r]=score[l]; return; }
    int tmp;
    for (int i=l; i<=r; ++i){
        dfs(l, i-1);
        dfs(i+1, r);
        tmp=f[l][i-1]*f[i+1][r]+score[i];
        if (tmp>f[l][r]){ f[l][r]=tmp; root[l][r]=i; }
    }
}

void print(int l, int r){
    if (l>r) return;
    if (l==r) printf("%d ", l);
    else {
        printf("%d ", root[l][r]);
        print(l, root[l][r]-1);
        print(root[l][r]+1, r);
    }
}

int main(){
    for (int i=0; i<maxn; ++i)
        for (int j=0; j<maxn; ++j)
            f[i][j]=1;
    scanf("%d", &n);
    for (int i=1; i<=n; ++i)
        scanf("%d", &score[i]);
    dfs(1, n);
    printf("%d
", f[1][n]);
    print(1, n);
    return 0;
}