[数据结构与算法]加分二叉树（DP，记忆化搜索）

https://www.luogu.com.cn/problem/P1040

题意：给定一棵二叉树的前序遍历为1 2 3…n，二叉树的分数计算方式为：左子分数*右子分数+根节点分数，求：一种前序遍历达到该二叉树的最大得分。

分析：我们可以枚举1…n的节点为根节点，假设这次枚举的根节点为k，左子树的节点范围就是1到k-1，右子树是k+1到r。

设计DFS(l,r)去搜索节点范围l，r以谁为根分数最大即可。

#include <bits/stdc++.h>
//题意，对于一颗中序遍历已经确定的二叉树，如何确定前序遍历能让二叉树得分最高

using namespace std;

long long n,dp[50][50];
long long s[50][50],a[50];
long long DFS(int l,int r)
{
    if(l>r)
        return 1;
    if(l==r)
    {
        s[l][r]=l;
        return a[l];
    }
    if(dp[l][r])
        return dp[l][r];
    int score=0,num=-1;
    for(int i=l;i<=r;i++)
    {
        int temp=DFS(l,i-1)*DFS(i+1,r)+a[i];
        if(temp>score)
        {
            score=temp;
            num=i;
        }
    }
    s[l][r]=num;
    dp[l][r]=score;
    return score;
}
void preorder(int l,int r)
{
    if(l>r)
    return;
    cout<<s[l][r]<<" ";
    preorder(l,s[l][r]-1);
    preorder(s[l][r]+1,r);
}
int main()
{
	 cin>>n;
	 for(int i=1;i<=n;i++)
     {
         cin>>a[i];
     }
     cout<<DFS(1,n)<<endl;
     preorder(1,n);
	return 0;
}