【题解】洛谷P1040 [NOIP2003]加分二叉树

题目

洛谷P1040加分二叉树

题解

在中序遍历的序列中,每个子区间对应一棵树,如果确定了根节点,那么该节点左侧是左子树,右侧是右子树,可以区间dp。

代码

Subscribe
提醒
guest
1 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年9月14日 下午8:33

【小白解析】
此题的二叉树实现效果与《线段树1》类似,本质均是根节点k表示区间[l,r],其左右子树分别表示[l,k-1]与[k+1,r]。l,r,k在此均表示数据sc[l/r/k]是第l/r/k个读进的数据(正确性有待考察);因而作为二叉树,其储存性质正好满足中序遍历时,数据按读取顺序先进先出:

void dfs(int l,int r) //白嫖一下博主的代码,中序遍历(仅作演示,正确性亦有待考察)

{

if(rt[l][r]>l) dfs(l,rt[l][r]1);

printf(“%d “,rt[l][r]);

if(rt[l][r]<r) dfs(rt[l][r]+1,r);

}

f[l][r]表示[l,r]区间计算所得的最大值;rt[l][r]表示[l,r]区间隶属根节点的序号;22至25行的操作即为动态分配的基本判断。