#3719

Дубы

Темы: [Динамическое программирование по подстрокам]

На аллее перед зданием Министерства Обороны в ряд высажены n дубов. В связи с грядущим приездом главнокомандующего, было принято решение срубить несколько деревьев для придания аллее более милитаристического вида.

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

если и ближайший дуб слева, и ближайший дуб справа строго ниже, чем данный дуб;
если и ближайший дуб слева, и ближайший дуб справа строго выше, чем данный дуб.

В частности, согласно этому правилу, нельзя срубить крайний левый и крайний правый дубы.

Министр хочет выработать такой план вырубки, чтобы в итоге осталось несколько дубов, высоты которых образуют неубывающую последовательность, то есть чтобы каждый дуб был не ниже, чем все дубы, стоящие слева от него. При этом, как человек любящий флору, министр хочет, чтобы было срублено минимальное возможное количество деревьев.

Помогите сотрудникам министерства составить оптимальный план вырубки аллеи или выяснить, что срубить дубы соответствующим образом невозможно.

Входные данные

Первая строка входного файла содержит целое число n — количество дубов, растущих на аллее (2 ≤ n ≤ 200). Вторая строка содержит n чисел — высоты дубов, приведенные слева направо. Высоты дубов — положительные целые числа, не превышающие 1 000.

Выходные данные

Если оставить последовательность дубов с неубывающими высотами невозможно, выходной файл должен содержать только одно число - 1.

В случае, если искомый план существует, в первую строку выходного файла выведите целое число m — минимальное количество дубов, которые необходимо срубить. В следующие m строк выведите оптимальный план вырубки деревьев — номера дубов в том порядке, в котором их следует срубать, по одному номеру на строке.

Дубы нумеруются слева направо натуральными числами от 1 до n.

Если планов с наименьшим числом срубаемых дубов несколько, выведите любой из них.

Примеры

Входные данные

5
3 2 4 8 5

Выходные данные

2
2
4

#3780

Компьютерная игра (платформы)

Темы: [Динамическое программирование: один параметр]

Вы можете вспомнить хоть одного своего знакомого до двадцатилетнего возраста, который в детстве не играл в компьютерные игры? Если да, то может быть вы и сами не знакомы с этим развлечением? Впрочем, трудностей при решении этой задачи это создать не должно.

Во многих старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой-нибудь герой прыгает по платформам (или островкам), которые висят в воздухе. Он должен перебраться от одного края экрана до другого. При этом при прыжке с одной платформы на соседнюю, у героя уходит |y₂–y₁| единиц энергии, где y₁ и y₂ — высоты, на которых расположены эти платформы. Кроме того, у героя есть суперприём, который позволяет перескочить через платформу, но на это затрачивается 3·|y₃–y₁| единиц энергии. Конечно же, энергию следует расходовать максимально экономно.

Предположим, что вам известны координаты всех платформ в порядке от левого края до правого. Сможете ли вы найти, какое минимальное количество энергии потребуется герою, чтобы добраться с первой платформы до последней?

Входные данные

В первой строке записано количество платформ n (1 ≤ n ≤ 30000). Вторая строка содержит n натуральных чисел, не превосходящих 30000 — высоты, на которых располагаются платформы.

Выходные данные

Выведите единственное число — минимальное количество энергии, которую должен потратить игрок на преодоление платформ (конечно же в предположении, что cheat-коды использовать нельзя).

Примеры

Входные данные

2
100 1

Выходные данные

Входные данные

3
1 100 80

Выходные данные

#3782

Abcdefg (малые ограничения)

Темы: [Динамическое программирование: два параметра]

Есть сообщение, записанное в алфавите из N символов. Известно, что 1-й, 2-й, ..., N-й символы алфавита использованы в сообщении f₁, f₂, ..., f_N раз. Его необходимо набрать на M-клавишной клавиатуре, используя способ набора, аналогичный используемому в мобильных телефонах.

На телефоне, клавише 2 сопоставлены буквы abc, клавише 3 — def, и т.д. Для набора текста телефон переводится в специальный режим, в котором одно нажатие на клавишу 2 порождает символ a, 2 подряд нажатия на 2 символ b, 3 подряд символ c; аналогично, одно нажатие 3 порождает d, 2 подряд e и т. д. Если же необходимо набрать 2 подряд буквы a, то нажимают клавишу 2, немного ждут и снова нажимают клавишу 2.

В нашем случае, символы с 1-ого по некоторый K₁-ый должны соответствовать 1-ой клавише, с (K₁ + 1)-ого по некоторый K₂-ой — 2-ой клавише и т. д., до K_M = N. Конкретные значения K₁, K₂, ..., K_M - 1 не задаются — их, наоборот, нужно подобрать.

Напишите программу, которая будет искать минимальное необходимое количество нажатий на клавиши для набора указанного сообщения на указанной клавиатуре.

Входные данные

В первой строке содержатся два числа N и M, во второй — N чисел f₁, f₂, ..., f_N — количества вхождений соответствующего символа. Числа внутри строк разделены одинарными пробелами. 2 ≤ M ≤ 50, 3 ≤ N ≤ 70, M < N, 1 ≤ f_i ≤ 1000.

Выходные данные

Необходимо вывести единственное число — найденное минимальное количество нажатий на клавиши.

Примечание к примеру тестов

Значение 21 достигается при K₁ = 2, K₂ = 3 (1-й и 2-й символы сопоставить 1-й клавише, 3-й символ 2-й клавише, 4-й и 5-й символы 3-й клавише). Тогда количество нажатий будет

(3 × 1 + 2 × 2) + (5 × 1) + (7 × 1 + 1 × 2) = 21.

Примеры

Входные данные

5 3
3 2 5 7 1

Выходные данные

#3783

Abcdefg (полные ограничения)

Темы: [Динамическое программирование: два параметра]

(Задача отличается от предыдущей исключительно ограничениями на N и M.)

Есть сообщение, записанное в алфавите из N символов. Известно, что 1-й, 2-й, ..., N-й символы алфавита использованы в сообщении f₁, f₂, ..., f_N раз. Его необходимо набрать на M-клавишной клавиатуре, используя способ набора, аналогичный используемому в мобильных телефонах.

На телефоне, клавише 2 сопоставлены буквы abc, клавише 3 — def, и т.д. Для набора текста телефон переводится в специальный режим, в котором одно нажатие на клавишу 2 порождает символ a, 2 подряд нажатия на 2 символ b, 3 подряд символ c; аналогично, одно нажатие 3 порождает d, 2 подряд e и т. д. Если же необходимо набрать 2 подряд буквы a, то нажимают клавишу 2, немного ждут и снова нажимают клавишу 2.

В нашем случае, символы с 1-ого по некоторый K₁-ый должны соответствовать 1-ой клавише, с (K₁ + 1)-ого по некоторый K₂-ой — 2-ой клавише и т. д., до K_M = N. Конкретные значения K₁, K₂, ..., K_M - 1 не задаются — их, наоборот, нужно подобрать.

Напишите программу, которая будет искать минимальное необходимое количество нажатий на клавиши для набора указанного сообщения на указанной клавиатуре.

Входные данные

В первой строке содержатся два числа N и M, во второй — N чисел f₁, f₂, ..., f_N — количества вхождений соответствующего символа. Числа внутри строк разделены одинарными пробелами. 2 ≤ M ≤ 500, 3 ≤ N ≤ 700, M < N, 1 ≤ f_i ≤ 1000.

Выходные данные

Необходимо вывести единственное число — найденное минимальное количество нажатий на клавиши.

Примечание

Значение 21 достигается при K₁ = 2, K₂ = 3 (1-й и 2-й символы сопоставить 1-й клавише, 3-й символ 2-й клавише, 4-й и 5-й символы 3-й клавише). Тогда количество нажатий будет

(3 × 1 + 2 × 2) + (5 × 1) + (7 × 1 + 1 × 2) = 21.

Примеры

Входные данные

5 3
3 2 5 7 1

Выходные данные

#3789

Сохранить энергию

Темы: [Динамическое программирование: два параметра]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2011, Задача D ]

Одна Фруктовая Компания, производящая электронику, решила озаботиться длительностью работы своих смартфонов от аккумулятора.

Выяснилось, что процессор, который они закупают у азиатского поставщика, поддерживает m различных режимов работы, при этом каждая из k операций языка программирования (который Фруктовая Компания использует для написания всех своих программ) может быть выполнена в каждом из режимов. Одновременно процессор может работать только в одном режиме, но перед выполнением каждой из операций можно один раз переключиться в любой другой режим работы.

Известно количество единиц энергии, которое тратится для исполнения каждой из операций в каждом режиме, а также сколько энергии тратится на переключение между режимами. Требуется написать программу, определяющую, какое минимальное количество энергии необходимо потратить для выполнения заданной программы.

В начале выполнения программы процессор находится в первом режиме, завершиться выполнение программы может при любом режиме процессора.

Входные данные

Первая строка содержит три целых числа: число k (1 ≤ k ≤ 100) — количество операций в языке программирования, число m (1 ≤ m ≤ 100) — количество режимов работы, которое поддерживает процессор, и число n (1 ≤ n ≤ 10000) — количество операций в исследуемой программе.

Следующие k строчек содержат по m целых неотрицательных чисел, не превышающих 100. j-е число в i-ой строчке обозначает, сколько энергии тратится на выполнение i-ой операции в j-ом режиме команд.

Далее следует m строчек, содержащих по m целых неотрицательных чисел, не превышающих 100. j-ое число в i-ой строчке обозначает, сколько единиц энергии тратится на переключение процессора с режима i на режим j. Гарантируется, что в i-ой строке i-ое число равно 0.

Последняя строчка содержит исследуемую программу: n натуральных чисел, не превышающих k и соответствующих операциям языка программирования.

Выходные данные

Выведите одно число — минимальное количество единиц энергии, необходимое для выполнения программы.

Подзадачи и система оценки

Тесты к этой задаче состоят из трех групп.

Тесты из условия, оцениваются в ноль баллов.
В тестах этой группы \(n\), \(m\), \(k\) не превосходят 10. Эта группа оценивается в 50 баллов, баллы ставятся только при прохождении всех тестов группы.
В тестах этой группы \(m\) не превосходит 10. Эта группа оценивается в 30 баллов, баллы ставятся только при прохождении всех тестов группы и предыдущих групп.
В тестах этой группы дополнительные ограничения отсутствуют. Группа оценивается в 20 баллов, баллы ставятся только при прохождении всех тестов этой и предыдущих групп.

Примеры

Входные данные

Выходные данные

Входные данные

Выходные данные