加分二叉树

题意:给定一个不知道树的情况的中序遍历,然后求左子树的值乘右子树的值再加上根节点的值,然后求这个的最大值
题解:我知道这个咋说....树形dp还是记忆化搜索,好像都差不多,基本上都是发挥计算机,算的快的优越性的暴力........
中序遍历结果:
left表示左子树的区间,right表示右子树的区间,就是以root根节点来划分左右子树
枚举每一个点为树的根节点,然后再以当前位置,枚举其左子树的最大值和右子树的最大值
递归遍历,可以加上记忆化搜索减少次数
然后每次对所求区间的最大值式子如下:

第i个节点为划分左右子树节点,咦有点像区间dp
时间复杂度:我瞎猜一个 .....这种递归的不咋会计算........逃......

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
ll tree[100];//输入数组
ll val[100][100];//区间(l,r)的最大值
ll root[100][100];//回溯根节点
ll ans=0;
ll dfs(int l,int r)
{
    if(l>r)
        return 1;//如果l>r，说明子树为空，题目有说明若子树为空默认为1
    if(l==r)
    {
        root[l][r]=l;
        return tree[l];
        //若l=r，说明在叶子节点上，这种节点的根就是它自己。
    }
    if(val[l][r])
        return val[l][r];
    //这里是记忆化搜索的应用，即如果此区间的值已经被计算过，就不再用dfs(l,r)求其值，而使用val[][]数组中已经保存的值。
    //因为val初始值是0，所以只要val不等于0即表示此区间已经被计算过
    for(int i=l; i<=r; i++)
    {
        //这里是枚举根节点，从l-r，i为根节点编号。
        int temp=dfs(l,i-1)*dfs(i+1,r)+tree[i];
        //计算当i为此节点编号时i子树的加分
        //这三个分别对应：
        //subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数。
        if(temp>val[l][r])
        {
            root[l][r]=i;
            val[l][r]=temp;
        }
        //如果i为根节点的子树加分 大于 已有的区间的加分，则保存其根节点和加分。
    }
    return val[l][r];
    //返回 记忆化搜索

}
void print(int l,int r)
{
    if(l>r)
        return;
    printf("%d ", root[l][r]);
    print(l,root[l][r]-1);
    print(root[l][r]+1,r);
}
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>tree[i];
    }
    dfs(1,n);
    cout<<val[1][n]<<endl;
    print(1,n);
}

题解2:区间dp
板子区间dp式子还是上面那个式子,然后三层循环

选取中间点,对左右区间进行dp
时间复杂度:

#include<iostream>
#include<cstdio>
using namespace std;
int n,v[39],f[47][47],i,j,k,root[49][49];
void print(int l,int r){
    if(l>r)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() {
    scanf("%d",&n);
    for( i=1; i<=n; i++) scanf("%d",&v[i]);
    for(i=1; i<=n; i++) {f[i][i]=v[i];f[i][i-1]=1;}
    for(i=n; i>=1; i--)
        for(j=i+1; j<=n; j++)
            for(k=i; k<=j; k++) {
                if(f[i][j]<(f[i][k-1]*f[k+1][j]+f[k][k])) {
                    f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];
                    root[i][j]=k;
                }
            }
    printf("%d\n",f[1][n]);
    print(1,n);
    return 0;
}