Автор: | И. Бураго | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 64 Мб | |
Выходной файл: | output.txt |
Дан целочисленный вектор P1, P2, …, PN. Над любым вектором, состоящим из двух и более элементов, определим операцию сжатия, состоящую в замене произвольной пары соседних элементов на их сумму. Например, вектор 123 в результате сжатия может превратиться в вектор 33 либо 15.
Требуется путем последовательного применения операции сжатия получить из исходного вектора вектор максимально возможной длины, все элементы которого не меньше A и не больше B.
Входной файл содержит тройку чисел N A B, за которой следует N чисел P1, P2, …, PN.
Выходной файл должен содержать длину результирующего вектора, за которой следуют его элементы. Если решений не существует, вывести единственное число 0. Если решений несколько, вывести любое из них.
Все числа во входном файле целые.
1 ≤ N ≤ 1000, 0 ≤ A, B, pi ≤ 106.
№ | Входной файл (input.txt ) |
Выходной файл (output.txt ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|
Поскольку в одной операции сжатия участвуют только два соседних элемента, исходная задача эквивалентна выделению в заданном векторе групп последовательных элементов, подлежащих суммированию. Будем решать поставленную задачу методом динамического программирования.
Фиксируем некоторое R (1 ≤ R ≤ N) и рассмотрим участок исходного вектора с 1-го по R-й элемент включительно. Обозначим за TR длину наилучшего решения на этом отрезке, а за SL,R — сумму элементов вектора с L-го по R-й. Ясно, что TR определяется как разность R и количества операций сжатия, произведенных на рассматриваемом интервале.
Крайнее на текущем фрагменте R-е число может быть просуммировано с 0, 1, …, R − 1 элементами, стоящими слева от него. Оставим в рассмотрении только те из этих вариантов, при которых получающаяся сумма SL,R находится в диапазоне от A до B. В таком случае для каждого L (1 ≤ L ≤ R) возможно выразить решение на рассматриваемом интервале через наилучшее сжатие фрагмента вектора с 1-го по (L − 1)-й элементы. Действительно, при условии, что элементы с L-го по R-й будут заменены единственным числом, наилучшее решение определяется сжатием первых L − 1 элементов вектора.
Таким образом, рассматриваются все возможные для R-го элемента варианты, т. е.
TR = maxL(TL − 1 + 1).
Здесь при вычислении максимума необходимо перебрать все L, для которых существует решение на фрагменте c 1-го по (L − 1)-й элементы и одновременно выполнены условия:
1 ≤ L ≤ R,
A ≤ SL,R ≤ B.
Последовательное рассмотрение всех возможных значений R дает в конечном итоге ответ — длину TN искомого вектора.
По условию задачи также требуется установить не только длину оптимального решения, но и сам результат сжатия. Результирующий вектор состоит из TN элементов. Его вычисление удобно начинать с конца. Для этого необходимо для каждого R помимо TR запомнить еще и значение LR, при котором достигается максимум. Тогда последний элемент будет равен сумме элементов исходного вектора с LN-го по N-й, предпоследний — сумме элементов с LLN − 1-го по LN − 1-й, и т. д.