дп


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи ПрогрессПопытки, все/успешные
ID 93202. Ёлочная гирлянда
Темы: Строки    дп    жадные алгоритмы    *1300   

Ёлочная гирлянда состоит из n лампочек, пронумерованных от 1 до n. Каждая лампочка либо горит (обозначим «1»), либо не горит («0»). Текущее состояние гирлянды задано строкой a.

Монтажник Егор хочет, чтобы гирлянда выглядела по-праздничному — в виде строки b (тоже из нулей и единиц, той же длины n). Менять строку b нельзя — это «образец».

С гирляндой a Егор может выполнять две операции:

  • Переключить одну лампочку. Выбрать позицию i (1 ≤ i ≤ n) и поменять её состояние (0 → 1 или 1 → 0). Стоимость такой операции — 1 рубль.
  • Поменять местами две лампочки. Выбрать две позиции i и j (1 ≤ i, j ≤ n) и поменять состояния этих лампочек местами. Стоимость такой операции — |i - j| рублей, то есть расстояние между позициями.

Помогите Егору найти минимальную суммарную стоимость, с которой можно превратить гирлянду a в гирлянду b.
 

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

В первой строке — целое число n (1 ≤ n ≤ 106) — количество лампочек в гирлянде.

Во второй строке — строка a длины n, состоящая только из символов «0» и «1», — текущее состояние гирлянды.

В третьей строке — строка b длины n, состоящая только из символов «0» и «1», — желаемое состояние гирлянды.
 

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

Одно целое число — минимальная суммарная стоимость, которую нужно заплатить, чтобы превратить a в b.

 /
ID 91202. Великая Цепь Курсов
Темы: дп    *1700   

Штурманский журнал «Нулевого указателя» содержит n записей о курсах корабля — каждая запись это целое число (градусы поворота за день). Капитан Архипов считает, что самый красивый маршрут — это когда курсы идут строго последовательными целыми числами: x, x+1, x+2, … Он называет это Великой Цепью.

Найдите наидлиннейшую подпоследовательность записей (не обязательно подряд), которая образует Великую Цепь. Выведите её длину и номера записей в журнале. Если существует несколько подпоследовательностей максимальной длины — можно вывести любую.

«И не вздумай вывести только длину», — добавил Архипов, не отрываясь от чая.


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

Первая строка: n (1 ≤ n ≤ 200 000).

Вторая строка: n чисел ai (1 ≤ ai ≤ 109) — курсы по дням.


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

Первая строка: длина наибольшей Великой Цепи.

Вторая строка: номера записей в порядке возрастания (нумерация с 1).

 

Примечание: Журнал: 5 3 1 2 4 1 3 (7 записей).

Записи №3, 4, 5, 7 имеют курсы 1, 2, 3, 4 — они идут подряд с шагом 1, образуя Великую Цепь длиной 4.

Например, записи №1, 2, 7 дают курсы 5, 3, 3 — не подходят (не последовательные).

Записи №6, 4, 5 дают 1, 2, 4 — тоже не подходят (пропущено 3).

Если существует несколько подпоследовательностей максимальной длины — можно вывести любую.

 8/ 2
ID 91198. Зелье от морской болезни
Темы: Бинарный поиск    реализация    дп    *1100   

Шкипер Баг ужасно страдает от морской болезни. Единственное спасение — зелье «Штиль», которое продаётся в лавках на островах архипелага. На n островах цены разные: в i-м порту бутылка стоит xi дублонов.

Каждый раз, когда «Нулевой указатель» заходит в порт, у Шкипера Бага с собой разная сумма — зависит от того, не украл ли корабельный кот монеты из кармана. Всего таких заходов будет q. Для каждого захода Шкипер Баг хочет заранее знать: в скольких портах архипелага он смог бы купить зелье, имея столько дублонов?

Формат входных данных
Первая строка: n (1≤n≤100 000) — количество портов.
Вторая строка: n чисел  xi​ (1≤xi≤100 000) — цены на зелье.
Третья строка: q (1≤q≤100 000) — количество заходов в порт.
Следующие q строк: число mi​ (1≤mi≤109) — дублоны Шкипера Бага при i-м заходе.

Формат выходных данных
q чисел — для каждого захода количество портов, где хватит денег.


Примечание: 
При 1 дублоне ни одна лавка недоступна. При 8 — можно купить в 4 лавках (цены 2, 3, 4, 7). При 3 — только одна лавка (цена 2). При 100 дублонах — все пять.

 38/ 4