Could anyone please exlain me how to solve this dp problem? Link:https://atcoder.jp/contests/dp/tasks/dp_n Help?
Could anyone please exlain me how to solve this dp problem? Link:https://atcoder.jp/contests/dp/tasks/dp_n Help?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | jiangly | 3578 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | tourist | 3565 |
| 8 | maroonrk | 3531 |
| 9 | Radewoosh | 3521 |
| 10 | Um_nik | 3482 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 8 | SecondThread | 146 |
| 10 | pajenegod | 145 |
Check this out... https://www.codechef.com/JULY19B/problems/CIRMERGE/
It also has a nice editorial.
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
please can you tell me what's the problem with greedy solution in this problem? when i use this solution it give me WA
the greedy solution based on at each move we select 2 adjacent elements with the lowest sum, and merge them until one element remaining.
In greedy approach, we are making sure that cost incurred in each of the progressive step is minimum but this may not result in minimum total cost incurred.
this video by Errichto helped me a lot while solving the dp atcoder contest : https://www.youtube.com/watch?v=FAQxdm0bTaw&t=8731s
hint for someone who wants to try:
dp[i][j]state refers to the minimum total cost of combining interval[i,j]into one vertex. answer will bedp[0][n-1]Is there anything I am missing? If someone can help ?
Link : My solution
Update to
cost=1e18;and it works.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;ccan be larger thanINT_MAXIf 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.
can someone tell me what's the problem with greedy solution in this problem? when i use this solution it give me WA
the greedy solution based on at each move we select 2 adjacent elements with the lowest sum, and merge them until one element remaining.