luogu_P1040 [NOIP2003 提高组] 加分二叉树

打印 上一主题 下一主题

主题 920|帖子 920|积分 2760

P1040 [NOIP2003 提高组] 加分二叉树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题意:给你一颗中序遍历为1到n的二叉树,和每个节点的val。树的值=左子树的值×右子树的值+根的val,空树值为1,求整个树最大值和这个值树的前序遍历。
题解:区间dp。dp[l][r]表示最大值,root[l][r]表示最大值的根,枚举区间然后枚举根,根据题目中的计算公式搞最大值。
  树形dp。一样的dp[l][r]表示子树罢了。
  多想想,一步步讨论就好了,关键是找能做出答案的状态表示再想转移方程。
int n,a[N],dp[N][N],rt[N][N];
void pre_ans(int l,int r){
    if(l>r) return;
    couta,dp=a,rt=i;
    for(int len=1;len
回复

使用道具 举报

0 个回复

倒序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

愛在花開的季節

金牌会员
这个人很懒什么都没写!

标签云

快速回复 返回顶部 返回列表