每日一题 5.13 加分二叉树

唉 天天摸鱼导致一感冒 好点后再写题解都超时了
虽然没牛币可以白嫖但还是写写自己的理解吧
这题我们要抓住中序遍历的特点 以根节点划分左子树右子树
这样就可以不断递归下去求
解法就出来了 区间dp dp[i][j]表示i-j区间二叉树划分的分数最大
前序遍历就是每次求最大时记录下根节点即可

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 35;
int dp[N][N],pre[N][N],a[N],n;
void dfs(int l,int r) {
    if(l>r) return;
    int k=pre[l][r];
    cout<<k<<" ";
    dfs(l,k-1);
    dfs(k+1,r);
}
int main() {
    cin>>n;
    for(int i=0;i<=n;++i)
     for(int j=0;j<=n;++j)
          dp[i][j]=1;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        dp[i][i]=a[i];  ///i-i区间
        pre[i][i]=i;
    }
    for(int len=2;len<=n;++len)///区间长度
    {
        for(int i=1;i+len-1<=n;++i)///起始点
        {
            int j=i+len-1;///终点
            dp[i][j]=0;
            for(int k=i;k<=j;++k)
            {
                ll v=dp[i][k-1]*dp[k+1][j]+a[k];///遍历求最大
                if(dp[i][j]<v)
                {
                    dp[i][j]=v;
                    pre[i][j]=k;///记录i-j区间的根节点
                }
            }
        }
    }
    cout<<dp[1][n]<<endl;
    dfs(1,n);///根据前序遍历的特点输出
    return 0;
}