Динамическое программирование

ФД начинает с одного генома и редактирует его, выполняя следующие шаги:

1. Разделяет геном между каждыми двумя последовательными равными символами.
2. Реверсирует каждую из полученных подстрок.
3. Конкатенирует реверсированные подстроки в том же порядке.

Например, если ФД начинает с генома AGGCTTT, то он выполнит следующие шаги:

1. Разделит между последовательными равными символами G и T получит AG | GCT | T | T.
2. Реверсирует каждую подстроку, получит GA | TCG | T | T.
3. Конкатенирует реверсированные подстроки, получит GATCGTT.

К несчастью, после редактирования генома компьютер ФД сломался, и ФД потерял последовательность генома, с которого он начинал. Более того, некоторые части отредактированного генома повредились, заменившись на знак '?'.

По заданной последовательности отредактированного генома помогите ФД определить количество возможностей для стартового генома по модулю \(10^9+7\).

Бовинополис состоит из ряда из \(N\) пастбищ (\(1 \leq N \leq 3 \cdot 10^5\)), Каждое из которых содержит одну корову типа Holstein или Guernsey.

Правительство Бовинополиса хочет разделить его на некоторое количество непрерывных районов так, чтобы каждый район содержал не более \(K\) пастбищ (\(1 \leq K \leq N\)), и каждое пастбище содержится ровно в одном районе. Поскольку сейчас правительство контролируется Holstein-ами, они хотят найти такой способ разделения на районы, который минимизирует количество районов, в которых коров Guernsey будет больше, чем коров Holstein или столько же сколько Holstein.

Оппозиционная коалиция Guernsey старается выяснить вред от такого переадминистрирования. Помогите им вычислить минимальное количество районов, в которых у Guernsey будет большинство или равенство.

ФД рассердился. Он приделал к стене счётчик дней с последнего слома. Если слом случился утром, счётчик покажет 0. Если последний слом случился 3 дня назад, счётчик показывает 3. ФД тщательно записывал значение счётчика каждый день.

В конце года ФД решил действовать. Однако с логом некоторые проблемы.

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

\(N\) коров (\(1 \leq N \leq 10^4\)) ФД стоят в ряд, последовательно пронумерованные \(1 \ldots N\). Корова \(i\) имеет \(s_i\) - уровень мастерства в заворачивании подарков. ФД решил объединить коров в команды. Команда состоит из любого последовательного множества коров числом не более \(K\) коров (\(1 \leq K \leq 10^3\)), и корова не может быть более чем в одной команде. Поскольку коровы могут учиться друг у друга, уровень мастерства каждой коровы в команде может быть заменен на уровень мастерства самой мастеровитой коровы.

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

Сколькими способами ФД может покрасить оставшиеся амбары?

€Ја  ­ зЁ­ Ґвбп б Ї®б«Ґ¤®ў вҐ«м­®бвЁ Ё§ \(N\) Ї®«®¦ЁвҐ«м­ле 楫ле зЁбҐ« (\(2 \leq N \leq 262,144\)), Є ¦¤®Ґ ў ¤Ё Ї §®­Ґ \(0 \ldots 40\). ‡  ®¤Ё­ 室 ЃҐбЁ ¬®¦Ґв ‚§пвм ¤ў  б®бҐ¤­Ёе а ў­ле зЁб«  Ё § ¬Ґ­Ёвм Ёе ­  зЁб«® ­  1 Ў®«миҐ (­ ЇаЁ¬Ґа, ®­  ¬®¦Ґв § ¬Ґ­Ёвм ¤ўҐ б®бҐ¤­ЁҐ 7 ­  ®¤­г 8). –Ґ«м ЁЈал - ¬ ЄбЁ¬Ё§Ёа®ў вм §­ зҐ­ЁҐ б ¬®Ј® Ў®«ми®Ј® зЁб« , Є®в®а®Ґ ®­  ¬®¦Ґв Ї®«гзЁвм. Џ®¬®ЈЁвҐ Ґ©.

Џђ€Њ…ђ ‚‚Ћ„Ђ:

4
1
1
1
2

Џђ€Њ…ђ ‚›‚Ћ„Ђ:

3

‚ ЇаЁ¬ҐаҐ ЃҐбЁ б­ з «  б«Ёў Ґв ўв®аго Ё ваҐвмо 1 Ё Ї®«гз Ґв Ї®б«Ґ¤®ў вҐ«м­®бвм 1 2 2 ,   § вҐ¬ б«Ёў Ґв ¤ўҐ ¤ў®©ЄЁ ў 3. ‡ ¬ҐвЁ¬, зв® ­Ґ ®ЇвЁ¬ «м­® б«Ёў вм ЇҐаўлҐ ¤ўҐ Ґ¤Ё­Ёжл.

Ђўв®а: Mark Chen Bessie likes downloading games to play on her cell phone, even though she does find the small touch screen rather cumbersome to use with her large hooves.

She is particularly intrigued by the current game she is playing. The game starts with a sequence of \(N\) positive integers (\(2 \leq N \leq 262,144\)), each in the range \(0 \ldots 40\). In one move, Bessie can take two adjacent numbers with equal values and replace them a single number of value one greater (e.g., she might replace two adjacent 7s with an 8). The goal is to maximize the value of the largest number she can create. Please help Bessie score as highly as possible!

Игра начинается с последовательности \(N\) положительных целых чисел (\(2 \leq N \leq 248\)), каждое в диапазоне \(0 \ldots 40\). На каждом ходу Беси может взять два числа с равными величинами и заменить их число на 1 больше. (Например, она может заменить две соседние 7 на одну 8). Цель игры - максимизировать наибольшее число, которое она может получить. Помогите Беси.

Игра начинается с последовательности \(N\) положительных целых чисел (\(2 \leq N \leq 248\)), каждое в диапазоне \(0 \ldots 40\). На каждом ходу Беси может взять два числа с равными величинами и заменить их число на 1 больше. (Например, она может заменить две соседние 7 на одну 8). Цель игры - максимизировать наибольшее число, которое она может получить. Помогите Беси.

ABCD
BXZX
CDXB
WCBA

Каждый день корова Беси прогуливается из верхнего левого угла в правый нижний, каждый раз двигаясь на один шаг вправо или вниз. Беси записывает в строку буквы, по которым прошлась. Она огорчится, если у неё получится палиндром (слово, которое читается одинаково слева направо и справа налево), поскольку тогда она запутается, в каком направлении двигалась.

Пожалуйста, помогите Беси определить количество различных маршрутов которыми она может получить палиндромы. Различные пути, которыми получаются одинаковые палиндромы учитывать множество раз. Выведите свой ответ по модулю 1,000,000,007.