-->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)$
-->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)$
Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com