Тяжелая ДП задача

Правка ru2, от DreamingBoy, 2016-12-14 12:07:20

Привет CodeForces.

Я не буду давать ссылку на задачу и даже объяснять условия задачи, потому-что эту задачу можно решить более легким способом. Но я хочу реализовать свою идею, но есть сложности в реализации и прошу вас помочь разобраться с этими сложностями.

В задаче требуется пересчитывать динамику

таким образом

Думаю есть способ быстро считать dp[i] = max(dp[j - 1] + (mx[j] - mn[j])) для 1 <= j < i

mx[j] -> максимум от j до i

mn[j] -> минимум от j до i

Заранее большое спасибо!

UPD: неужели это так тяжело, что никто не может помочь???

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru2 Русский DreamingBoy 2016-12-14 12:07:20 72 Мелкая правка: 'е спасибо!' -
en2 Английский DreamingBoy 2016-12-13 13:17:18 717 Tiny change: 'O(N ^ 2)\n~~~~~\n\' -
en1 Английский DreamingBoy 2016-12-13 12:56:26 857 Initial revision for English translation
ru1 Русский DreamingBoy 2016-12-13 09:55:33 856 Первая редакция (опубликовано)