Make Necklace Optimal#12834

Make Necklace Optimal (Editorial)

Денис Смірнов

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

Спочатку з'ясуємо як максимізувати вагу , якщо відомо, в якому елементі вона закінчується. Будемо підтримувати множину \{(x_1, v_1), (x_2, v_2), \dots, (x_k, v_k)\} для перших каменів, де — розмір останнього взятого каменя, а — найбільша сумма яку ми змогли досягнути, x_1 < x_2 < \dots < x_k, v_1 > v_2 > \dots v_k. Розглядаючи a_i ми можемо лише додати його до множин x_1 > \dots > x_l \geq a_i, помітимо, що серед них максимальна сума це v_l, тобто треба додати пару (x = a_i, v = v_l + a_i), але цим ми могли порушити впорядкованність , проте якщо a_i = x > x_j, a_i + x_l = v \geq v_j, то нам немає сенсу брати послідовність, що закінчується на x_j, ми можемо її лише покращити замінивши на , тому після видалення неоптимальних пар, властивість впорядкованності збережеться. Виконувати всі ці операції можно ефективно за допомогою std::map<int, int64_t>.

Таким чином, ми навчилися для кожної позиції з'ясовувати найважчу незростаючу послідовність, що закінчується в данному камені. Розвернувши масив, ми зможемо так само з'ясувати найважчу неспадну послідовність, яка починається у кожному камені. Далі, додавши найлегший камінь з X \cup Z, до і , ми можемо вважати що закінчується в тому самому елементі що починається , тобто нам треба знайти максимум з сум двох масивів, що ми знайшли вище (не забувши про те, що спільний елемент треба врахувати один раз).

Помітимо, що шукаючи оптимальну множину ми виконали ітерацій, на кожній з яких додали не більше одного елемента, скількись видалили та розглянули, лишивши у мапі, не більше одного, отже (видалень не більше ніж додавань) ми провели операцій з мапою. Отже, cкладність розв'язку: O(10 \cdot n \log n) = O(n \log n).