加分二叉树题解 记忆化搜索

根据中序遍历特性，在根节点前面的节点，一定在左子树；根节点后面的节点，一定在右子树。我们可以根据这个特性，结合递归的方式确定出最高加分的二叉树。我们每次查询的过程中，
查询max(dp[l][i-1]*dp[i+1][r]+ans[i]);

#include <bits/stdc++.h>
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define debug(x) cout << #x << ": " << x << endl;
#define debug1(x) cout<<"xxx"<<endl;
#define ll long long
#define ull unsigned long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#define mse(a,b) memset(a,b,sizeof a);
using namespace std;
const int maxx=1e6+100;
const int mod=1e9+7;
int ans[maxx];
int dp[35][35];
int root[35][35];
int pp=-0x3f3f3f;
void dfs(int l,int r)
{
    if(l>r)
    {
        dp[l][r]=1;
        return ;
    }
    if(l==r)
    {
        dp[l][r]=ans[l];
        root[l][r]=l;
        return ;
    }
    if(dp[l][r]==0)
    {
        for(int i=l;i<=r;i++)
        {
            dfs(l,i-1);
            dfs(i+1,r);
            int tem=dp[l][i-1]*dp[i+1][r]+ans[i];
            if(tem>dp[l][r])
            {
                dp[l][r]=tem;
                root[l][r]=i;
            }
            pp=max(pp,dp[l][r]);
        }
    }
}
void print(int l,int r)
{
    if(l>r) return ;
    cout<<root[l][r]<<" ";
    print(l,root[l][r]-1);
    print(root[l][r]+1,r);
}
int main()
{
   fio;
   int n;
   cin>>n;
   for(int i=1;i<=n;i++)
    cin>>ans[i];
   dfs(1,n);
   cout<<pp<<endl;
   print(1,n);
    return 0;
}