apnakaamkar's blog

N-Slimes(Atcoder)
By apnakaamkar, history, 6 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 (9)
| Write comment?
»
6 years ago, hide # |
 
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
»
6 years ago, hide # |
 
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
»
6 years ago, hide # |
 
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
»
6 years ago, hide # |
 
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
»
5 years ago, hide # |
 
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
  • »
    »
    5 years ago, hide # ^ |
     
    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
»
5 years ago, hide # |
 
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
»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

DP say the coset, marge to some grup (l to r ) slimes into one slime . and the final slimes size is sum of all slimes size ," whis make to marge (l to r ) slimes .

when l == r , the cose 0, becouse one slime . now make a for loop for( i = l; i<r; i++) this make make to deferent grup l to i and i+1 to r. find the cost to grup [l,i] and [i+1,r] and add the final slimes size [l,i] -> one slime whis size sum of all slime l to i. solv(): if l == r return 0; for( l to r-1 ) min[ sum l to i( final slime size l to i grup ) + sum i+1 to r + solv(l,i)[ cost to make one slime frome [l ,i ] grup ] + solv( i+1, r); ]

→ Reply