Hi Guys
I was reading this document point "2.1. The problem" and I was trying to implement the solution for (point "2.3.1. Leaves") http://vn.spoj.com/problems/NKLEAVES/en/ but I think I am missing something, my implementation fails even with example test case :(. Please, can someone help me with this problem.
Just in case, cij in the document is my function cost(i,j), F[n] is my dp[n][j], g in the document is the same g, but I send an extra parameter j the number of piles.
This kind of problems can be solved with convex hull trick
I learned this stuff after reading these links :
Codeforces Blog
Wikipeg
And after you solved the example problems in this blogs , i recommend to you try to solve
Arranging Heaps LA 2012
Yes, Arranging Heaps is almost the same problem (but with differents distances), but I am not able to understand the convex hull trick, as a first step I wanted to solve nkleaves unless you want to explain it to me? :D
I think that if you read carefully this links you can learn convex hull trick , i learned for my own reading this articles , if i can do it you can do it.
This two links have very good explanations.
I couldn't understand the second speed up technique mentioned in the pdf document, but can it solve a problem which convex hull trick can't solve? both NKLEAVES and IOI 2002 Batch Scheduling are application for that technique but both can be solved using convex hull trick