Блог пользователя gautam94

How to recover actual sequence of moves from a DP solution?
Автор gautam94, 10 лет назад, По-английски

I have written this code http://ideone.com/11kNYs for solving this problem http://codeforces.me/problemset/problem/219/C It asks for the minimum number of changes in a string such that no two adjacent characters are same and also only the first k characters can be used. The code is not yet complete as it's only calculating the minimum number of changes. The problem also requires the actual answer with minimum changes. So how to do this?

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

To recover the solution from the DP, whenever the answer for solve of (i,j) gets better (gets a smaller value than the present value) and say that solution is got from (k,l), then store (k,l) memo[i][j]. So we know that for each i,j how we got the best result. Now start iterating from the starting dp call. (n-1,'[') in your case and keep checking memo[i][j] until you get the base case. You can reconstruct the answer like that.

→ Ответить