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!