「NOIp2003」加分二叉树-记忆化搜索

题目描述

设一个\(n\)个节点的二叉树\(tree\)的中序遍历为\(（1,2,3,…,n）\)，其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为\(d_i\),\(tree\)及它的每个子树都有一个加分，任一棵子树\(subtree\)（也包含\(tree\)本身）的加分计算方法如下：

\(subtree\)的左子树的加分\(\times subtree\)的右子树的加分\(+ subtree\)的根的分数。

若某个子树为空，规定其加分为11，叶子的加分就是叶节点本身的分数。不考虑它的空子树。

试求一棵符合中序遍历为\(（1,2,3,…,n）\)且加分最高的二叉树\(tree\)。要求输出；

（1）\(tree\)的最高加分

（2）\(tree\)的前序遍历

Links

Luogu P1040

Solution

很明显的,题目给出的输入是一个中序遍历,因此一个节点的左子树必定在序列中它的左边,一个节点的右子树必定在序列中它的右边,因此可以通过枚举中间节点进行记忆化搜索,在输出部分,因为题目要求输出前序遍历,那么使用一个数组在每次发生更新时存储区间\([left,right]\)的父亲节点,输出时,先输出当前区间的父节点,然后递归的输出左子树和右子树即可

Code

#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline T read(){
    T sum=0;
    int fl=1,ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') fl=-1;
    for(;isdigit(ch);ch=getchar()) sum=(sum<<3)+(sum<<1)+ch-'0';
    return sum*fl;
}

const int maxn=50+5;

int n;
int a[maxn][maxn];
int v[maxn];
int root[maxn][maxn];

int dfs(int l,int r){
    if(a[l][r]>0) return a[l][r]; //记忆化
    if(l==r) return v[l]; //当前查找到的为单点,直接返回
    if(r<l) return 1; //没有子树,加分为1
    for(int i=l;i<=r;i++){
        int tmp=dfs(l,i-1)*dfs(i+1,r)+a[i][i];
        if(tmp>a[l][r]){
            a[l][r]=tmp;
            root[l][r]=i;
        }
    }
    return a[l][r];
}

void print(int l,int r){
    if(r<l) return;
    if(l==r){
        printf("%d ",l);
        return;
    }
    printf("%d ",root[l][r]); //先输出根
    print(l,root[l][r]-1);//再输出左子树
    print(root[l][r]+1,r);//最后输出右子树
}

int main(){
    n=read<int>();
    for(int i=1;i<=n;i++){
        v[i]=read<int>();
        a[i][i]=v[i];
    }
    printf("%d\n",dfs(1,n));
    print(1,n);
    return 0;
}