加分二叉树（P1040）

Len_zh · 2023-03-31 20:37:09 · 个人记录

加分二叉树

众所周知，一般而言，随着经济社会的发展...

（以上省略114514字）...今天，小编就来给大家带来 加分二叉树 的...

首先看题，题目是一棵已知节点数的二叉树，每个节点都有一定分值，还已知分值的运算公式，很明显是一道DP，而且可以用区间DP

原理：

对每个节点i，求出1-i的最大分数，并借此求得1-n的最大分值

对每个节点，用root[l][r]存储树。l和r以及数值分别表示树的l与r之间存在节点root[l][r]下方有子树

转移方程

转移方程很好写，就是从头d到尾，用f[i] [j]表示i与j之间的最短距离，而l表示i与j的距离，用k表示中间的分叉点，则有

f【i】【j】=max（f【i】【k-1】（左树）*f【k+1】【j】（右树）+f【k】【k】（节点）

输出子树

由于root中已经存储了树的形态，只要将树以根−>左−>右输出即可，考虑递归。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll root[1000][1000],f[1000][1000];
ll n;

void input()
{
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>f[i][i];
        f[i][i-1]=1;
        root[i][i]=i;
    }
}

void out(ll l,ll r)
{
    if (l>r)return;
    cout<<root[l][r]<<" ";
    if (l==r)return;
    out(l,root[l][r]-1);
    out(root[l][r]+1,r);
}
signed main()
{
    input();
    for (int l=1;l<n;l++){
        for(int i=1;i<=n-l;i++){
            int j=l+i;
            f[i][j]=f[i+1][j]+f[i][i];
            root[i][j]=i;
            for(int k=i+1;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;
                }
            }
        }
    }
    cout<<f[1][n]<<endl;
    out(1,n);
    return 0;
}