Оптимизация акции

Сначала решим задачу за . Это можно сделать при помощи динамики  — минимальная стоимость разбиения префикса массива длины i. Пересчет , , где  — сумма максимумов на подотрезке . В момент пересчета мы можем идти по j от i - 1 до 0, поддерживая текущие элементы массива на подотрезке в std: : multiset и аккуратно пересчитывая сумму минимумов.

Чтобы решить задачу быстрее, надо понять, что нам всегда выгодно брать отрезки либо длины 1, либо длины 10. Предположим мы взяли отрезок длины меньшей 10, тогда его стоимость не зависит от разбиения и его можно разбить на отрезки длины 1, предположим мы взяли отрезок длины , , тогда мы можем оставить из этого отрезка оптимальный подорезок длины 10, а все что по краям взять отрезками длины 1. Если длина отрезка равна 20, то, очевидно, не хуже взять его как два отрезка длины 10. В остальных случаях можно также предъявить разбиение на подотрезки длины 1 и 10, которое будет не дороже исходного.

Делать пересчет для отрезков длины 1 легко, чтобы делать пересчеты для отрезка длины 10, можно хранить элементы из отрезка в любой структуре данных, умеющей брать минимум быстро. Например очередь с минимумом или std: : multiset.

Асимптотика .