Блог пользователя chinese

Автор chinese, история, 9 лет назад, По-русски

Подскажите как решить задачу : click

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Осортируем массив, воспользуемся динамикой dp[pref] — ответ для префикса pref. dp[i] = min(dp[i], max(dp[j], maximum-minimum)), где j от 1 до i-2, maximum и minimum — максимум и минимум на отрезке j+1..i соответственно. База dp[0] = 0, dp[1..n] = infinity