树形dp/记忆化搜索

首先可以看出树形dp，因为第一个问题并不需要知道子树的样子，

然而第二个输出前序遍历，必须知道每个子树的根节点，需要在树形dp过程中记录，递归输出

那么如何求最大加分树——根据中序的特征，想到以枚举根结点为起点那么轻易得出如果根结点的编号为x，那么左子树的结点有1~x-1，右子树 结点有x+1~n

 

#include
     
      #include
      
       #include
       
        using namespace std;int n,d[30];int f[30][30];int rt[30][30];int dfs(int l,int r){    if(l>r)return 1;//无儿子    if(l==r){        rt[l][r]=l;return d[l];    }    if(f[l][r])return f[l][r];    int ans=0,root;    for(int i=l;i<=r;i++){
   //枚举根         int tmp=dfs(l,i-1)*dfs(i+1,r)+d[i];        if(tmp>ans){            ans=tmp;            root=i;//根         }    }    rt[l][r]=root;    f[l][r]=ans;    return ans;}void print(int l,int r){    if(l>r)return;    printf("%d ",rt[l][r]);    print(l,rt[l][r]-1);    print(rt[l][r]+1,r);}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)scanf("%d",&d[i]);    printf("%d\n",dfs(1,n));    print(1,n);}