Мои Конспекты
Главная | Обратная связь


Автомобили
Астрономия
Биология
География
Дом и сад
Другие языки
Другое
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Металлургия
Механика
Образование
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Туризм
Физика
Философия
Финансы
Химия
Черчение
Экология
Экономика
Электроника

Пример №3: Пилообразная последовательность




Обозначим пилообразную последовательность длины N как последовательность, у которой для каждого не крайнего элемента выполняется условие: он или меньше обоих своих соседей или больше. Требуется посчитать количество пилообразных последовательностей из цифр длины N. Выглядит это как-то так:

Решение

 

Динамика по подотрезкам


Это класс динамики, в котором состояние — это границы подотрезка какого-нибудь массива. Суть в том, чтобы подсчитать ответы для подзадач, основывающихся на всех возможных подотрезках нашего массива. Обычно перебираются они в порядке увеличения длины, и пересчёт основывается, соответственно на более коротких отрезках.

Пример №4: Запаковка строки


Вот Развернутое условие. Я вкратце его перескажу:

Определим сжатую строку:
1) Строка состоящая только из букв — это сжатая строка. Разжимается она в саму себя.
2) Строка, являющаяся конкатенацией двух сжатых строк A и B. Разжимается она в конкатенацию разжатых строк A и B.
3) Строка D(X), где D — целое число, большее 1, а X — сжатая строка. Разжимается она в конкатенацию D строк, разжатых из X.
Пример: “3(2(A)2(B))C” разжимается в “AABBAABBAABBC”.

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

Решение

 

Пример №5: Дубы