Задача E. "Ну-ка, покатились!"
Рассмотрим решение с помощью метода динамического программирования.Пусть Di - минимальный штраф, который мы заплатим, если будем решать задачу для шариков с номерами от i до n, причем шарик номер i будет обязательно приколот.
Тогда
где
Если числа S(i, j) не считать каждый раз, а пересчитывать, используя формулу S(i, j) = S(i, j - 1) + xj - xi, то решение требует всего O(n) памяти и O(n2) времени на решение.
Важное замечание: в приведенных рассуждениях, шарики нужно рассматривать в порядке увеличения их координат.
когда человек не знаком с ней, сложно объяснить, откуда что берется. Просто размышления по другому пути идут.
Потому что ДП - это в некотором смысле даже стиль мышления, и научиться так мыслить по теории вообще не очень получится. Некоторые базовые знания получить необходимо, важно разобрать основные типичные задачи.
Но дальше - только практика поможет.
Если не поможет - тогда дам тест
Шарики катятся налево, и поэтому можно и без модуля. А цена булавки - это число ci.
вначале все шарики сортим
f[1,1]=c[1];
f[i,j], где i- это шарик который мы сейчас берем, а j- это последний шарик до i, который мы прикололи
для j<i f[i,j]=f[i-1,j]+x[i]-x[j]
для j=i f[i,j]=минимум из всех f[i-1]+с[i];
Ответ: минимум из всех f[n];
P.S эта динамика требует больше памяти, чем та которая представлена в разборе, но на мой взгляд ее легче понять
Let $$$dp[i][0]$$$ be the minimum cost of reaching ith coordinate such that ith coordinate is pinned. and let $$$dp[i][1]$$$ be the minimum cost of reaching ith coordinate such that ith coordinate is not pinned. and let $$$dp[i][2]$$$ be the number of balls free for sliding at $$$i^{th}$$$ coordinate. Then suppose $$$dp[i][0] = min(dp[i - 1][0], dp[i - 1][1] + dp[i -1][2] * dist) + cost[i]$$$
and if $$$dp[i - 1][0] > dp[i - 1][1] + dist * dp[i - 1][2]$$$ then $$$dp[i - 1][1] = dp[i - 1][0]$$$ else $$$dp[i - 1][0] = dp[i - 1][1] + dp[i - 1][2] * dist$$$.
TLDR; I couldn't find bugs in my proof, any help highly appreciated! Also, can anyone prove the greedy algorithm? Thanks!