Нова робота для Валл-І#172

Нова робота для Валл-І (Розбір)

Що обмежує робота насправді. Коробки лежать у робочому контейнері відсортованими за зростанням, і брати можна лише верхню. Коробку в прокрастинаційний контейнер можна лише прибрати — назад її не дістати. Отже коробка з номером потрапляє на полицю тільки після того, як усі менші номери вже або розставлені, або викинуті. Висновок:

номери розставлених коробок утворюють зростаючу послідовність.

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

Переформулювання. Нехай — позиція полиці з номером на доріжці. Треба вибрати якнайдовшу зростаючу послідовність номерів v_1 < v_2 < \ldots < v_m так, щоб послідовність \mathrm{pos}[v_1], \ldots, \mathrm{pos}[v_m] розбивалася щонайбільше на монотонних шматків, які по черзі зростають і спадають. При K = 1 це рівно задача про найдовшу зростаючу підпослідовність перестановки — і саме так її й треба розв'язувати, лише в шарах.

Динаміка. Обробляємо проходи k = 1, 2, \ldots, K, а всередині кожного — значення від до (тобто в тому самому порядку, у якому коробки виходять зі стосу). Для поточного проходу тримаємо дерево Фенвіка на максимум над позиціями:

\mathrm{dp}[v] = 1 + \max \begin{cases} \text{найкраще на цьому ж проході з меншою позицією (запит до Фенвіка)},\\ \text{найкраще з \emph{попередніх} проходів при меншому } v . \end{cases}

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

Для парних проходів позиції мають спадати. Щоб не писати другий варіант коду, індексуємо дерево Фенвіка з протилежного кінця: замість позиції беремо N + 1 - q. Тоді «менша позиція» знову означає «префікс», і код той самий.

Наприкінці кожного проходу оновлюємо M[v] \leftarrow \max(M[v], G[v]), де — префіксний максимум по цьому проходу. Відповідь — .

Складність — \mathcal{O}(K \cdot N \log N), що за N \le 10^5 і K \le 100 цілком проходить. Дерево Фенвіка на максимум із повним переініціалізуванням на кожному проході — додатково, це дрібниця.