问个DP沙雕板子题,除了楼主都会

回复帖子

@天泽龟  2019-02-12 09:49 回复

给定一个初始数列,数列内部元素互相加(可以自己加自己)得到新的元素加入数列,问排序后的第n项是多少?

有点像NOIP2018D1T2,N<100000,a[i]<INT范围。

应该是裸的DP不会,wcsl

@杜岱玮 2019-02-12 10:07 回复 举报

@天泽龟 两个heap,一个大根堆,一个小根堆,维护相同的集合。一开始就是初始序列。之后循环以下操作直到集合不发生改变:1.找到两个最小元素相加得到新元素加入集合2.弹出最大的元素直到集合大小小于N

@杜岱玮 2019-02-12 10:08 回复 举报

需要一个堆删除的小技巧,要不写个BBST也可以。最后最大元素即为答案

@杜岱玮 2019-02-12 10:18 回复 举报

三楼的算法好像只是没考虑两个相同元素相加的情况,把这个特判一下就好了

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。