加分二叉树

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

subtree text{subtree} subtree 的左子树的加分 × times × subtree text{subtree} subtree 的右子树的加分 + + + subtree text{subtree} subtree 的根的分数。

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

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

1. tree text{tree} tree 的最高加分。

2. tree text{tree} tree 的前序遍历。

第 1 1 1 行 1 1 1 个整数 n n n，为节点个数。

第 2 2 2 行 n n n 个用空格隔开的整数，为每个节点的分数

第 1 1 1 行 1 1 1 个整数，为最高加分（$ Ans le 4,000,000,000$）。

第 2 2 2 行 n n n 个用空格隔开的整数，为该树的前序遍历。

5
5 7 1 2 10

145
3 1 2 4 5

对于全部的测试点，保证 1 ≤ n < 30 1 leq n< 30 1≤n<30，节点的分数是小于 100 100 100 的正整数，答案不超过 4 × 1 0 9 4 times 10^9 4×109。

状 态 表 示 ： f [ i ] [ j ] ： 从 第 i 个 结 点 到 第 j 个 结 点 作 为 一 个 单 独 的 树 的 最 大 加 分 状态表示：f[i][j]：从第i个结点到第j个结点作为一个单独的树的最大加分 状态表示：f[i][j]：从第i个结点到第j个结点作为一个单独的树的最大加分

转 移 方 程 : f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i ] [ k − 1 ] ∗ f [ k + 1 ] [ j ] + f [ k ] [ k ] ) 转移方程:f[i][j]=max(f[i][j],f[i][k-1]*f[k+1][j]+f[k][k]) 转移方程:f[i][j]=max(f[i][j],f[i][k−1]∗f[k+1][j]+f[k][k])

正确性的证明：

d p dp dp的核心就在于：过去百分百的决定现在，并且这种决定状态能够延伸到未来

我们第一层循环枚举区间长度，这样我们在调用状态 转 移 方 程 : f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i ] [ k − 1 ] ∗ f [ k + 1 ] [ j ] + f [ k ] [ k ] ) 转移方程:f[i][j]=max(f[i][j],f[i][k-1]*f[k+1][j]+f[k][k]) 转移方程:f[i][j]=max(f[i][j],f[i][k−1]∗f[k+1][j]+f[k][k])的时候，其子树的最大加分一定已经被求出来了，因为我们枚举的区间长度是从小到大的，所以满足了过去百分百的决定现在的性质。最后输出 f [ 1 ] [ n ] f[1][n] f[1][n]即可

#include 
using namespace std;
#define int long long
const int N=2*30+5;
int f[N][N];
int root[N][N];
int n;

void print(int l,int r)
{
    int k=root[l][r];
    cout<=l)
    {
        print(l,k-1);
    }

    if (r>=k+1)
    {
        print(k+1,r);
    }

}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>f[i][i];
        root[i][i]=i;
    }

    for(int len=1;len
        for(int l=1;l+len<=n;l++)
        {
            int r=l+len;
            for(int k=l;k<=r;k++)
            {
                int val;
                if (k==l)
                {
                    val=f[l+1][r]+f[l][l];
                }
                else if (k==r)
                {
                    val=f[l][r-1]+f[r][r];
                }
                else
                {
                    val=f[l][k-1]*f[k+1][r]+f[k][k];
                }

                if (val>f[l][r])
                {
                    f[l][r]=val;
                    root[l][r]=k;
                }
            }
        }
    }
    cout< 
记忆化搜索：
 
#include 
using namespace std;
#define int long long
const int N=2*30+5;
int f[N][N];
int root[N][N];
int n;

int search(int l,int r)
{
    if (f[l][r])
    {
        return f[l][r];
    }
    for(int k=l;k<=r;k++)
    {
        int l_val=(k==l?1:search(l,k-1));
        int r_val=(k==r?1:search(k+1,r));

        if (l_val*r_val+f[k][k]>f[l][r])
        {
            f[l][r]=l_val*r_val+f[k][k];
            root[l][r]=k;
        }
    }
    return f[l][r];

}
void print(int l,int r)
{
    int k=root[l][r];
    cout<=l)
    {
        print(l,k-1);
    }

    if (r>=k+1)
    {
        print(k+1,r);
    }

}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>f[i][i];
        root[i][i]=i;
    }


    cout<