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

Need Help in GCD Partitions [Dynamic Programming]
Автор Makise_Kurisu, 4 года назад, По-английски

Hi, I was trying to solve this problem. And after going through a couple of submissions (Here is a neat one) I got the transition recurrence but I am still not able to work around the intuition behind it. Can someone please explain a little about what are the pointers which lead you this recurrence and also I am sorry if it's a standard dp type(if possible please share some resource or problem based on the same idea :P)

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

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

Let

$$$f(i, j) = \text{maximum sum if we partition the first i elements in j parts}$$$

Then the answer is clearly f(n, k). The recurrence relation is

$$$f(i, j) = \displaystyle\max_{k < i}f(k, j-1) + \text{GCD}(a[k+1], \dots, a[i])$$$

with the base case being f(i, 1) = GCD(a[1],..,a[i]).

You can find my implementation here.

The trick about such DP problems is to think of the right states. Then the recurrence will be pretty obvious. This, however, needs some practice. If I recall correctly, in the book Competitive Programming 3 there is a note in the Dynamic Programming chapter where the authors present some common states in DP problems. With enough practice you should be able to find the correct states more often.

→ Ответить