加分二叉树-DP

题目来源：Acwing 479-加分二叉树&NEFU OJ-353 加分二叉树
NEFU OJ题源为多组输入，代码为此oj ac代码

题目描述

设一个n个节点的二叉树tree的中序遍历为（1,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的前序遍历

输入描述

第1行：一个整数n，为节点个数（n<30） 。
第2行：n个用空格隔开的整数，为每个节点的分数（0<分数<100）。

输出描述

第1行：一个整数，为最高加分（结果不会超过int范围）。     
第2行：n个用空格隔开的整数，为该树的前序遍历。如果存在多种方案，则输出字典序最小的方案。

输入样例

5
5 7 1 2 10

输出样例

145
3 1 2 4 5

OP

y总yyds

思路

首先明确分数计算方式，对于一般的树而言，分数=左树*右树+根分数
如果左树或右树为空，且不均为空，则空树分数视为1；
若左右数均空，则空树分数均视为0，此时分数则仅为根分数。

这道题采用从叶子向根的DP过程，建立 d[ i ][ j ] 表示 [ i , j ] 区间内所有元素构成分数最大的数的分数值。限定该区间的长度，在 [ 1 , n ] 区间从短到长进行DP。

具体的DP过程：
在区间长度为len，左端点 i ，右端点 j = i + len - 1 时，以 k 为区间树的根，d[ i ] [ j ] = max( d[ i ][ k - 1 ] * d[ k + 1 ][ j ] + a[ k ] )。

接下来进行特判：
如果len==1，即 i == j 时，左右子树均为空，d[ i ][ j ] = a[ i ]；
如果 k == i，即仅左子树为空，左子树分值为 1；
如果 k == j，仅右子树为空同理。

接下来处理输出要求：
因为要求是前序遍历，故遍历 k 时从左到右即可满足条件，即所有可行解中最小 k。并记录区间树的根节点，输出时按根节点分为两树分别递归即可。

代码

#include <bits/stdc++.h>

using namespace std;
int a[30],f[30][30],d[30][30]= {0},n,i,j,k,len;
//a存储节点分数，f存储[i,j]区间树最大分数值，d存储[i,j]区间树最大分数值时的序号最小根（输出用）
void dfs(int l, int r)//递归输出
{
    if (l > r) return;//结束条件不是i==j
    printf(" %d",f[l][r]);
    dfs(l, f[l][r] - 1), dfs(f[l][r] + 1, r);//以区间树的根节点为界分成两个区间
}
int main()
{
    while(cin>>n)
    {
        memset(d,0,sizeof d);
        for(i=1; i<=n; i++)scanf("%d",&a[i]);
        for(len=1; len<=n; len++)//遍历合法区间长
            for(i=1; i<=n-len+1; i++)//遍历合法左端点
            {
                j=i+len-1;//计算对应区间长和左端点的右端点
                if(len==1)f[i][j]=i,d[i][j]=a[i];//特判叶子
                else
                {
                    for(k=i; k<=j; k++)//遍历合法根
                    {
                        int lef=(k==i)?1:d[i][k-1];//定义左子树分数
                        int rig=(k==j)?1:d[k+1][j];//定义右子树分数
                        int ans=a[k]+lef*rig;//计算以k为根的区间树分数
                        if(ans>d[i][j])d[i][j]=ans,f[i][j]=k;//与历史值比较（如果是>=，就不是字典序最小答案了）
                    }
                }
            }
        printf("%d\n",d[1][n]);
        printf("%d",f[1][n]);//此行及下行如果不担心PE的话可以直接用dfs(1,n)代替
        dfs(1,f[1][n] - 1),dfs(f[1][n] + 1, n);
        printf("\n");
    }
    return 0;
}

ED

\