I've been trying to understand how to solve this problem on UVa: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=441&page=show_problem&problem=3969

Abridged problem statement: You have N piles in different heights, each pile having a weight W. You can only move a pile if the next X is bigger than the pile you are moving, and each move costs W * Δ Height. You want to turn the N piles into K piles with the minimum cost possible (you can only move one pile to another place where there was a pile). constraints: 1 ≤ K ≤ N ≤ 1000 and W ≤ 10⁶

I've found lots of explanations (mostly in spanish and chinese), and all of them say "it's easy to see a DP solution of O(n*n*k), but that would TLE..." yeah, I can see one DP solution in O(n*n*k), but I can't understand their recursion and, more specifically, how to turn that into line equations and how to apply convex hull trick on it.

I've never solved any problem that needed convex hull trick or any DP optimization at all, so I'm quite a noob here. Any materials (apart from PEGWiki's article on convex hull trick), like simple problems solvable with it, are apreciated.

Thanks!

References (didn't help me, but maybe some of you can make sense out of it):

• C++ Implementation: https://github.com/marioyc/Online-Judge-Solutions/blob/master/UVA/Contest%20Volumes/12524%20-%20Arranging%20Heaps.cpp

• Explanation in spanish: http://chococontest.wordpress.com/2012/11/25/solucionario-regional-south-america-2012/

• Explanation in chinese (according to Google translate):http://blog.csdn.net/work_freedom/article/details/8915965