Помогите решить задачку.
Есть массив чисел. Надо разбить его на n отрезков, так чтобы минимизировать суммарный риск для всех отрезков. Риск для одного отрезка это произведение длины отрезка на сумму чисел на нем.
Ограничения: Длина массива < 8000
n < 800
Числа в массиве < 1e9
Ссылка на задачу https://www.hackerrank.com/contests/ioi-2014-practice-contest-2/challenges/guardians-lunatics-ioi14
я не уверен, но мне кажеться divide and conquer optimization
Простоя динамика будет
dp[i][j] = min{dp[i — 1][k] + C(k, j)}
где C(k, j) = (sum[j] — sum[k]) * (j — k)
sum[j] = сумма на префиксе
Должно выполняться условие:
C[a][d] + C[b][c] ≥ C[a][c] + C[b][d] where a < b < c < d.
Вроде у меня на бумажке выполняется, или же где-то ошибся.
Спасибо