[洛谷 1040][NOIP2003]加分二叉树

题目链接

https://www.luogu.org/problem/P1040

题解

一道树形 DP 的题，难度也不算太大。

首先考虑第一问：因为给的是中序遍历，所以可以枚举根节点，继而得出左右子树，然后按定义递归求解（这里要记忆化搜索，不然递归层数过多可能导致 TLE 或者是 RE）。

我们枚举根节点 \(i\)，得到如下转移方程：

$$f_{l,r}=\max(f_{l,i-1} \times f_{i+1,r}+s_i)$$

然后是第二问：在更新最优解的时候，可以把该子树的根节点存下来，然后就可以递归输出了。

#include <stdio.h>
#include <string.h>
int f[305][305],ino[305],s[305],root[305][305];
int calc(int l,int r)
{
 if(l>r)return 1;//空树
 else if(~f[l][r])return f[l][r];//记忆化
 else if(l==r)return s[l];//叶节点
 int ans=0;
 for(int i=l;i<=r;i++)//枚举根节点 
 {
  int x=calc(l,i-1)*calc(i+1,r)+s[i];
  if(x>ans)
  {
   root[l][r]=i;
   ans=x;
  }
 }
 return f[l][r]=ans;
}
void print_tree(int l,int r)
{
 printf("%d ",root[l][r]);
 if(l<=root[l][r]-1)print_tree(l,root[l][r]-1);//输出左子树 
 if(root[l][r]+1<=r)print_tree(root[l][r]+1,r);//输出右子树 
 return;
}
int main()
{
 int n;
 memset(f,-1,sizeof(f));
 scanf("%d",&n);
 for(int i=1;i<=n;i++)
  scanf("%d",&s[i]);
 for(int i=1;i<=n;i++)
  root[i][i]=i;
 printf("%d\n",calc(1,n));
 print_tree(1,n);
 return 0;
}