12
18
2015
0

[bzoj]4345: [POI2016]Korale

-->http://www.lydsy.com/JudgeOnline/problem.php?id=4345

 

首先考虑第一个问题

定义二元组$(x,y)$表示当前价值为$x$，位置在$y$，则$(x,y)$可以转移到$(x+a[y+1],y+1)$以及$(x-a[y]+a[y+1],y+1)$两个状态，这个先把$a$数组排序，再加个小根堆维护就行了，复杂度$\mathcal{O}\left(k\log k\right)$

Category: bzoj | Tags: 堆 线段树 暴力

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com