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

# | User | Rating |
---|---|---|

1 | Benq | 3796 |

2 | tourist | 3722 |

3 | Radewoosh | 3719 |

4 | ecnerwala | 3578 |

5 | ksun48 | 3462 |

6 | Um_nik | 3456 |

7 | maroonrk | 3445 |

8 | jiangly | 3431 |

9 | Petr | 3370 |

10 | scott_wu | 3350 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 207 |

2 | awoo | 186 |

3 | rng_58 | 184 |

4 | Errichto | 182 |

5 | SecondThread | 177 |

5 | Radewoosh | 177 |

7 | -is-this-fft- | 176 |

7 | maroonrk | 176 |

9 | Um_nik | 173 |

10 | antontrygubO_o | 170 |

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

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/16/2021 03:36:28 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

It also has a nice editorial.

thanks

build a 2d matrix of size n x n. start from bottom like what if you had only one element in the array, then solve for two elements , then three then you will eventually develop a recurrence relations by just manually solving it. just to confirm you will only have to fill the half dp table when it is cut diagonally , step 1: fill 1,1 2,2 3,3 4,4 till n,n step 2 : fill 1,2 2,3 3,4 till n-1,n step3 while filling 1,3 and so on

thanks

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

Recursion with memorisation

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

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

Link : My solution

Update to

`cost=1e18;`

and it works.Why cant we use priority queue here? like https://www.geeksforgeeks.org/connect-n-ropes-minimum-cost/

Choose two adjacent slimes, and combine them into a new slime. They must be adjacent.Am i missing something in this solution: https://atcoder.jp/contests/dp/submissions/22675988

`lli i,a, b = sum[endi]-sum[start-1],c=INT_MAX;`

`c`

can be larger than`INT_MAX`

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.

Yeah, that was the base upon which I built this solution. Thanks for pointing out the error.