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