How to solve this problem by using DP?

Revision en1, by Hd7, 2019-09-06 13:50:29

The problem VK2012 B — File List.
I solved it by using greedy, but this problem was tagged dp and the editorial instructed dp approach such that:

is [i] — can we cut the prefix of length i .

Initially, is [0] = 1, the remaining zeros.

Now iterate over i in ascending order and if is [i] = 1, try to make the transition to i  + 1 .. i  + 12

I still can't solve it by DP, could you give me a more detailed explanation to solve this problem using DP? Thanks in advance!

Tags #dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Hd7 2019-09-06 13:50:29 579 Initial revision (published)