Wednesday, 15 June 2011

dynamic programming - topcoder -



dynamic programming - topcoder -

i've been trying out dp tutorials on topcoder. 1 of problems given practice minipaint . think i've got solution partly- find minimum no. of mispaints given no. of strokes, each row , compute entire image (again using dp, similar knapsack problem). however, i'm not sure how compute min. no each row.

p.s later found match editorial, code finding min. no. of mispaintings each row seems wrong. explain they've done in code?

the stripscore() function returns minimum number of mispaintings each row given amount of strokes available paint it. although i'm not sure if rowid argument correct, thought starting @ start @ particular row needed amount of strokes available utilize , colour of part straight before it.

the key algorithm, best score area right of kth region, uniquely determined number of strokes needed, , color used paint (k-1)th region.

dynamic-programming

No comments:

Post a Comment