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

Подскажите как решить задачу с тренировки
Автор Obk, история, 9 лет назад, По-русски

Решил тут попробовать поучаствовать в тренировке. Понял, что даже А сложновата и решил посмотреть разбор — его не оказалось. Решения других людей посмотреть нельзя(????).

Условие задачи

Единственное упрощение, до которого я додумался — можно считать, что запросов одинаковой продолжительности меньше 3, поэтому n<=60 вместо n<=400 . Но для полного перебора это все равно многовато.

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

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

Пусть n<=60. Сделаем такую динамику dp[go][sum1][sum2] — мы прошли go запросов и отдали 1 серверу запросов на время sum1, а второму sum2(sum3 — вычисляется однозначно). Считаем эту ДП и находим лучшее из достижимых состояний.

Итого O(MAXT5 + N)

P.S. Видимо ещё надо сделать следующее: пусть есть 2 запроса длины х. Прибавим всем х и добавим запрос -x. Тогда запросов уже 30

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

Can we do it using standard dp knapsack approach (like in timus 1005)? We try to fill knapsack of size (sum of all requests/3) with all requests we have, then fill second knapsack of size (sum of what's left/2) with requests left. Will it or something like this work?

→ Ответить