Вот тут на контесте попалась такая вот ДП. Не могу понять, как решить. Вот условие :

Рассмотрим двухбуквенные последовательности, которые могут состоять только из букв a, b и при этом: 1.никогда не содержат двух букв b подряд, 2.ни в одном последовательности никогда не встречается три одинаковых подпоследовательности подряд. Например, этому правилу не удовлетворяют следующие последовательности: aaa (так как три раза подряд содержит a), ababab (так как три раза подряд содержит ab), aabababa (также три раза подряд содержит ab).

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

Формат входных данных

Вводится одно число K (1 ≤ K ≤ 100 000).

Формат выходных данных

Выведите одно число — количество различных двухбуквенных последовательностей длины K.

У меня получилась формула a[i] = a[i-1]+a[i-2]-x; Но вот что отнимать надо тут(этот пресловутый x), я не знаю.

Может кто-то поможет.

Большое спасибо!

Доброго времени суток. Есть такая задача — Лыжные гонки. Your text to link here...

Во время лыжных соревнований N спортсменов стартуют с интервалом в 1 минуту. Скорость каждого лыжника на дистанции постоянна: i-й лыжник преодолевает 1 км за wi минут. Длина трассы равна L км. Считается, что i-й лыжник обогнал j-го (совершил обгон), если он стартовал позже j-го, а пришёл к финишу раньше него. Подсчитайте суммарное число совершённых во время гонки обгонов.

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

Первая строка входного файла содержит два целых числа N и L. Во второй строке через пробел расположены N целых чисел wi.

1<=N<=500000, 1<=L<=10^9, 1<=Wi<=10^9

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

Выведите единственное число — суммарное количество обгонов.

Ограничение по времени — 2 сек Ограничение по памяти — 128\256 мб(не нашёл информации)

Что я придумал по этой задаче : будем идти по порядку, увеличивая i. i лыжник обгонит j, если i>j и L*Wi < L*Wj-(i-j). Что из этого следует — будем хранить в каждой вершине дерева отрезков отсотрированный массив, который относится к этой части ДО (деревом Ропана это вроде зовётся). И потом на каждый запрос мы будем log(N)*log(n) отвечать на этот запрос, сколько есть таких чисел на отрезке [1;i-1]. И на каждой итерации мы будем отнимать единицу от отрезка предыдущего.

Но квадрат логарифма судя по всему не зайдет. А логарифм зайдет. Как я придумал, тут нужно писать каскадирование. Это нам по идее обеспечит нужную асимптотику.

В чём вопрос : верна ли эта мысль? Если верна, то можете ли рассказать подробнее про это самое каскадирование и как его писать, если можно. Я ни разу его не писал и смутно представляю, как это сделать.

И ещё — нет ли других решений данной задачи?

Заранее спасибо.

Доброго времени суток! Имеются проблемы с задачей.Предыдущую тему удалил из-за другой проблемы, возникшей с этой задачей. Вот ссылка (задача С, Турнир) Your text to link here...

Вот само условие. Для тех, кто не хочет переходить по ссылке :

В турнире по хоккею участвовало K команд, каждая сыграла с каждой по одному матчу. За победу команда получала 2 очка, за ничью – 1, за поражение – 0 очков.

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

В первой строке входных данных содержится одно натурально число K, не превосходящее 100 – количество команд. Во второй строке задаются через пробел K целых неотрицательных чисел, не превосходящих 2(K–1), – количество очков, набранных командами, занявшими первое, второе, …, K-е места соответственно (то есть каждое следующее число не больше предыдущего). Выходные данные

Выведите турнирную таблицу в следующем формате. Таблица должна состоять из K строк с результатами игр команд, занявших первое, второе, …, последнее место (команды, набравшие одинаковое число очков, могут быть расположены в таблице в любом порядке). В каждой строке должно быть записано K чисел через пробел – количество очков, набранных в игре данной команды с первой, второй, … командами соответственно. Количество очков – это число 0, 1 или 2. В клетках на главной диагонали (соответствующих не существующей игре команды "самой с собой") нужно записать нули.

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

Я перепробовал множество алгоритмов : максимальный поток, много версий жадных алгоритмов, но максимум беру 70 % баллов.

Полного решения я просто не могу придумать. Может кто поможет с какой идеей?

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

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

Задача: Ограничения : Время работы — 1 секунда Огрничение по памяти — 256 мб.

Недавно на уроке во время контрольной Мария Ивановна перехватила записку Саше от Оли. Мария Ивановна очень хочет знать, что в записке, но, к сожалению, записка зашифрована. Мария Ивановна знает, что её ученики для шифровки заменяют каждую букву исходного сообщения на какую-то другую. Замена происходит таким образом, что одинаковые буквы всегда заменяются одной и той же буквой, а разные — разными.

Мария Ивановна подозревает, что записка — это ответы к контрольному тесту (ведь её длина случайно оказалась равной длине строки с правильными ответами). Однако она знает, что ответы Оли не обязательно полностью правильны. На каждый вопрос возможен один из K вариантов ответа. Естественно, Мария Ивановна знает правильные ответы.

Мария Ивановна решила расшифровать записку таким способом, чтобы максимизировать количество правильных ответов Оли. Однако, она очень занята, поэтому попросила Вас помочь ей в этом пустяковом деле.

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

В первой строке задана длина каждой из строк N (1 ≤ N ≤ 2 000 000) и K — количество возможных ответов на каждый вопрос (1 ≤ K ≤ 52). Ответы нумеруются в порядке abcde...xyzABCDE...XYZ. То есть, при K = 6 возможные ответы выглядят как abcdef, а при K = 30 "— abcde...xyzABCD.

Во второй строке задана зашифрованная записка — строка, состоящая из строчных и заглавных латинских букв.

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

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

В первой строке выведите единственное число — максимально возможное количество правильных ответов у Оли.

Во второй строке выведите расшифровку — строчку длины K, где по порядку для каждой буквы из шифра учеников указано, какому ответу она соответствует.

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

Очень прошу вас помочь!