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

Revision ru2, by 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: неужели это так тяжело, что никто не может помочь???

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru2 Russian DreamingBoy 2016-12-14 12:07:20 72 Мелкая правка: 'е спасибо!' -
en2 English DreamingBoy 2016-12-13 13:17:18 717 Tiny change: 'O(N ^ 2)\n~~~~~\n\' -
en1 English DreamingBoy 2016-12-13 12:56:26 857 Initial revision for English translation
ru1 Russian DreamingBoy 2016-12-13 09:55:33 856 Первая редакция (опубликовано)