apnakaamkar's blog

N-Slimes(Atcoder)
By apnakaamkar, history, 5 years ago, In English

Could anyone please exlain me how to solve this dp problem? Link:https://atcoder.jp/contests/dp/tasks/dp_n Help?

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Check this out... https://www.codechef.com/JULY19B/problems/CIRMERGE/

It also has a nice editorial.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Its easier to understand the recurrence relation from a solution done made with recursion (and memoisation), so here you go — https://atcoder.jp/contests/dp/submissions/15834404

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

this video by Errichto helped me a lot while solving the dp atcoder contest : https://www.youtube.com/watch?v=FAQxdm0bTaw&t=8731s

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there anything I am missing? If someone can help ?

Link : My solution

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Update to cost=1e18; and it works.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Am i missing something in this solution: https://atcoder.jp/contests/dp/submissions/22675988

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    lli i,a, b = sum[endi]-sum[start-1],c=INT_MAX; c can be larger than INT_MAX

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If you want to learn the concept behind this problem then go through Matrix chain multiplication DP, it is a very famous DP problem and has clear explanations(you can check Cormen or any online articles). This N-slimes problem is very similar to that but instead of multiplication, we do addition.

→ Reply