Плейлісти#518

Плейлісти (Розбір)

Спершу оцінимо, наскільки довгим може бути «чудовий» префікс. Умова a_i > \sum_{j<i} a_j означає, що після кожної пісні поточна сума більш ніж подвоюється. Рейтинги додатні, тому вже за пісні сума вискочить за межі 64-бітного типу. Отже, відповідь не перевищує — це ключ до всієї задачі.

Характеристика плейліста. Нехай ми починаємо слухати плейліст , маючи накопичену суму . Позначимо через \mathrm{pref}_j суму перших пісень плейліста. Тоді -та пісня не порушує «чудовість» тоді й лише тоді, коли

S + \mathrm{pref}_{j-1} < s_{i,j}, \qquad \text{тобто} \qquad S < s_{i,j} - \mathrm{pref}_{j-1}.

Тому введемо

\mathrm{md}_i(j) = \min_{t \le j} \bigl(s_{i,t} - \mathrm{pref}_{t-1}\bigr).

Перші пісень плейліста підходять рівно тоді, коли S < \mathrm{md}_i(j). Величину \mathrm{md}_i для всього плейліста назвемо його порогом T_i, а суму всіх його пісень — \Sigma_i.

У якому порядку брати плейлісти? Якщо ми беремо два плейлісти і повністю, то порядок «спочатку » допустимий за умови S < \min(T_a,\; T_b - \Sigma_a), а «спочатку » — за S < \min(T_b,\; T_a - \Sigma_b). Порівнявши ці дві межі, дістаємо класичний обмінний аргумент: вигідніше ставити раніше той плейліст, у якого менша сума

T_i + \Sigma_i.

Тому відсортуємо плейлісти за цією величиною — після цього оптимальний набір можна брати саме в цьому порядку.

Динаміка. Тепер це звичайний рюкзак «нуль-один» за кількістю пісень:

\mathrm{dp}[j] = \text{мінімальна досяжна сума, якщо повністю використано плейлісти сумарно на } j \text{ пісень.}

База \mathrm{dp}[0] = 0, а перехід для плейліста довжини k_i \le 63: якщо \mathrm{dp}[j - k_i] < T_i, то

\mathrm{dp}[j] \leftarrow \min\bigl(\mathrm{dp}[j],\; \mathrm{dp}[j - k_i] + \Sigma_i\bigr).

Мінімізуємо саме суму, бо чим вона менша, тим більше плейлістів можна причепити далі. Цикл по ідемо вниз, щоб кожен плейліст узявся щонайбільше раз. Плейлісти з T_i \le 0 або довжиною понад пропускаємо — вони непридатні.

Останній, неповний плейліст. Відповідь — це повністю прослуханих пісень плюс префікс ще одного плейліста. Для стану \mathrm{dp}[j] = S і плейліста кількість пісень, які ще вдасться взяти, — це найбільше з S < \mathrm{md}_i(t); оскільки \mathrm{md}_i незростаюча, це знаходиться двійковим пошуком.

Єдина тонкість: цей плейліст не має бути серед уже використаних. Тому разом із зберігаємо зв'язний список використаних плейлістів (кожен перехід запам'ятовує «попередній» вузол), і перед тим як подовжувати стан плейлістом , перевіряємо, чи його там немає — список має довжину щонайбільше .

Складність — \mathcal{O}(n \log n + n \cdot 63 + n \cdot 63^2), що при n \le 10^3 працює миттєво.