水的合集 1

集合挑选

从给定的N个集合中各挑出一个数并求和，求出前$K$大的$K$个和。

考虑如何从2个集合$A$,$B$中选出前$K$大。降序排序后$a_1$和$b_1$显然是最大，第二大则是$(a_1,b_2)$或者$(a_2,b_1)$。不妨以$(a_1,b_2)$来讲，那么第三大竞争者除$(a_2,b_1)$还有$(a_1,b_3)$，$(a_2,b_3)$……每对组合都能找到直接小于它的2个组合，而这种后继关系显然取遍了所有组合。仅需要前K大的我们按需扩展这一棵树即可。2个集合的前K大可与第3个集合执行相同的操作，从而得到最终答案。实际编写时，按照一定顺序限制扩展方向来保证每个方案仅访问一次，使用优先队列维护，复杂度为$O(\sum^N{K\log n_k}) \leq O(KN)$

LIS优化

可以发现，一旦有$a(k) < a(j), f(k) \geq f(j)$，j这个位置就没有用了。按照该规律维护一个单调栈记录，以长度单调（则数字a结尾的LIS自然单调）。此后转移