Тренування ніндзя#12992

Тренування ніндзя (Розбір)

Розв’яжемо задачу у зворотному порядку — додаватимемо вправи до програми. Нехай dp_i — довжина максимальної послідовності вправ, що задовольняє умови, якщо -та вправа виконується останньою.

Для кожної довжини зберігатимемо у pos_x всі позиції , де dp_j = x.

Коли додаємо вправу :