洛谷P1040 加分二叉树（树形dp）

#include<bits/stdc++.h>
usingnamespace std;
constint MAXN = 50;
typedef longlong ll;
ll n;
//f[i][j]表示i到j子树的最大分数 ll f[MAXN][MAXN],root[MAXN][MAXN]; 
void print(ll l, ll r) {
    if (l > r)return;
    cout<<root[l][r]<<"";//打印根 if (l == r)return;
    print(l, root[l][r] - 1);//打印左子树 
    print(root[l][r]+1,r);//打印右子树 }
int main()
{
    cin>>n;
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        cin>>f[i][i];
        root[i][i]=i;        
    }
    for(int len=1;len<n;len++)//以子树的长度遍历，1个节点的子树，2个节点的子树。。。     {
        for(int i=1;i+len<=n;i++)
        {
            int j=i+len;
            //根从i开始遍历，先假设i到j的子树，i为根 
            //不考虑它的空子树,所以左子树为空时，左子树为1，而不是0 
            //f[i][j]=f[i+1][j]+f[i][i];//此时i到j子树的分数
            //root[i][j]=i;
            //cout<<i<<"到"<<j<<" 最大为:"<<f[i][j]<<" 以"<<i<<"为根"<<endl; for(int k=i;k<j;k++)//k为根，遍历每一个根，找到能使子树分数最大的根             {
                 
                ll zhi = f[i][k-1]*f[k+1][j]+f[k][k];
                //不考虑它的空子树,所以左子树为空时，左子树为1，而不是0
                //以右子树为空时，右子树为1，而不是0if(f[i][k-1]==0)
                {
                    zhi=f[k+1][j]+f[k][k];
                }
                if(f[k+1][j]==0)
                {
                    zhi=f[i][k-1]+f[k][k];
                }                
                if(f[i][j]<zhi)
                {
                    f[i][j]=zhi;
                    root[i][j]=k;
                    //cout<<i<<"到"<<j<<" 最大为:"<<zhi<<" 以"<<k<<"为根"<<endl;                 }
            }
        }
    }
    cout<<f[1][n]<<endl;
    print(1, n);
    return0;
}