479. Additive binary tree (interval DP on the tree)

 

479. Add a binary tree - AcWing Question bank  

analysis ：

Conditions / nature ：

• In the sequence traversal 1,2,3...n
• The left and right subtrees are empty , integral =1
• Integral of subtree = Left * Right + root

Traversal according to the middle order is 1,2,3...n, It can be divided into the following situations

Root node =k, The left section is all l, All the sections on the right are r, The left and right sections are independent of each other

that , It can be converted into an interval dp, The model of stone merging , seek Break point As Root node

Note that the subtree is empty , Special consideration is needed when the subtree is empty

State means ：dp[i][j] Indicates that the traversal order of all middle orders is i~j Set

Recursive order ：1<=len<=n   ( Maybe it's just 1 Nodes )

initialization ： All for 0

The border ：dp[i][i]=w[i]

State calculation / subset division ：

  Because you need to enumerate [i~j] Who will be the root node in the set , There are three possible scenarios

• Only the left sub tree      j As the root node , The left sub tree is 1
• Only the right subtree      i As the root node , The right subtree is 1
• There are left and right subtrees       enumeration [i+1,j-1] One of them k As the root node

Enumerate the root nodes according to the left and right subtrees of the current tree , It can be divided into three sets

• The left subtree dp[l][k-1]   +    Root node w[k]   +    Right subtree dp[k+1][j]     

Depending on the break point , It can be divided into r-l+1 A subset of , Specifically =1 A rightless subtree +1 No left subtree + Multiple sets with left and right subtrees

For the result of preorder traversal , The former sequence traversal = Root left and right , So as long as Meiju chooses which one as the root node every time , That is to record what is chosen for each optimal decision

#include <iostream>
#include <algorithm>
using namespace std;
const int N=54;
int dp[N][N];
int w[N];
int g[N][N];

void dfs(int l,int r)
{
    if(l>r) return ;
    int p=g[l][r];
    cout<<p<<' ';
    dfs(l,p-1);
    dfs(p+1,r);
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>w[i];
    
    for(int len=1;len<=n;len++)
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            if(len==1)
                dp[i][j]=w[i],g[i][j]=i;    // By default, you use yourself as the root node 
            else
                for(int k=i;k<=j;k++)
                {
                    int left = k==i?1:dp[i][k-1];
                    int right = k ==j?1:dp[k+1][j];
                    int t=left*right+w[k];
                    if(t>dp[i][j])
                    {
                        dp[i][j]=t;
                        g[i][j]=k;
                    }
                }
        }
    cout<<dp[1][n]<<endl;
    dfs(1,n);
    return 0;
}