i was solving the cutting sticks problem frm UVA(10003) ...the approach i used was tht suppose there r 'n' cuts...so i used all the 2^n subsets of this as states...bt this approach is wasting too much time and memory..i read somewhere tht this problem is exactly similar to matrix chain multiplication..bt i can not figure out the similarity(i could nt convince myself tht i will get the solution doing tht way)...so can anyone explain hw to solve this problem...
here is the link to the problem...
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=944
here is the link to the problem...
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=944
Google Code Jam 2009, Round 1C Problem C
link: http://code.google.com/codejam/contest/dashboard?c=189252#s=a&a=2
it's a good tutorial!