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

题目链接

https://www.luogu.org/problemnew/show/P1040

题解

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

首先考虑第一问:因为给的是中序遍历,所以可以枚举根节点,继而得出左右子树,然后按定义递归求解(这里要记忆化搜索,不然递归层数会很吓人(可能是TLE也可能是RE))。

转移方程:\(f[l][r]=max(f[l][i-1]*f[i+1][r]+s[i])\)(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;
}

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注