dilingtian

分类

题解(18)

/ 注册

全部文章（共2篇）

题解 | #[NOIP2014]联合权值#

本题不能使用常规做法树形dp，因为相互之间没有联系，无法找到动态转换方程。所以我们换个思路，我们尝试遍历每个节点作为中转点，也可以称为根，那么它的两边的节点两两配对就可以符合题目的要求。我们将两边的节点的权值存入一个数组中，先排序，将数组的最后两个节点相乘就是本次最大的答案，不断更新就行。而且，...

前缀和树

2022-11-25

1 376

题解 | #小A的柱状图#

本题是找一个最大面积的矩形，图形是不能变换的，所以我们只需要先确定左右区间，再得到本区间的最小高度便可得到面积。我们可以通过栈的特点，确定第i个位置上的左端点和右端点，高度为h[i]。h[i]。h[i]。当我们遍历到第i个位置时，我们以h[i]h[i]h[i]为矩形高度，对于左右端点而言，增加高度...

栈前缀和

2022-11-06

1 384