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

Помогите с задачей
Автор chinese, история, 7 лет назад, По-русски

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

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

»
7 лет назад, # |
← 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

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    Что то не заходит. ты имел ввиду такое :

    for(int i = 1; i <= n; i++) 
for(int j = 0; j < i - 1; j++) if(dp[j] + a[i] - a[j + 1] < dp[i]) dp[i] = min(dp[i], dp[j] + a[i] - a[j + 1]), p[i] = j;
while(p[cur] != -1) {
    ans = max(ans, a[cur] - a[p[cur] + 1] );
    cur = p[cur];
}
cout << ans;
return 0;

    }

    ?

    → Ответить