Hello i have solved this problem kind of the same way i solved UVA 10003 — Cutting Sticks , after solving Cutting Sticks i did some research and find out about the Knuth-Yao optimization, even if i did not understand the code as a whole, i knew the basic condition and the answer, so i just plugged and played the code and got a very fast accepted con Cutting Sticks. As UVA 10688- The Poor Giant can be solve in a similar way to Cutting Sticks and obviously the condition dp[a][b-1]<=dp[a][b]<=dp[a+1][b] holds , can somebody tell me a way to manipulate the knuth-yao basic code to give right answer to this problem? :)
Of course a little explanation about the main Knuth-Yao code will also help a lot , thanks !!!
You said that "obviously the condition dp[a][b-1]<=dp[a][b]<=dp[a+1][b] holds". This is incorrect for this problem. Just because it seems like it works doesn't mean it actually does. Specifically this breaks on the 3rd sample case. However a different type of optimisation works.
Sorry i rushed on my conclusion (just because it is greatly similar), however which optimization can be use on this problem?
Using divide and conquer you can get (n^2)logn.
This uses the fact that a[i-1][j-1] <= a[i][j] (Where a is the optimal choice for the range, I assume that's what you meant by dp in your post).
Basically the outer loop is over range size, and use divide and conquer to calc all ranges of that size. To do this use a recursive function, keeping track of the current range of possible a's. (The first thing you calculate is the middle range, then recurse down).
well i tried to solve the problem using this idea but at the end i haven't come up with the solution at least for the D&C part, can you give me like an example? sorry to bother! thanks a lot