传送门:CF [前题提要]:赛时想不到怎么维护topk的方法,掉大分了.赛后发现该维护方法应该算一个挺典的trick,故记录一下 首先对于这道题,我们发现显然是需要使用dp,因为我们需要在最后输出前 k k k大的贡献,然后 n n n范围才 1 e 3 1e3 1e3,这一切都在暗示我们使用dp. 考虑如何使用dp,其实不难想到使用 d p [ i ] [ k ] [ 0 / 1 ] d