Модуль: Паттерны в динамическом программировании


Задача

1 /7


Количество сообщений

Теория Нажмите, чтобы прочитать/скрыть

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

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

Примерная схема решения такая:
dp[i] - ответ для первых i элементов

Подсчет dp[i]: так как мы рассматриваем только первые i элементов, то i-й будет последним и значит, что этот элемент будет в последнем подотрезке и при этом самым правым там. Поэтому мы можем перебрать левую границу последнего подотрезка j. В процессе перебора будем подсчитывать значение этого подотрезка и если он является корректным, то пересчитаем dp[i] через dp[j - 1] и значение подотрезка [j;i].

Рассмотрим следующую простую задачу: дан массив из целых чисел, необходимо разбить его на минимальное количество непересекающихся подотрезков, чтобы каждое число входило в какой-нибудь подотрезок и чтобы в каждом подотрезке были одинаковые числа. Например, для массива 1 2 2 3 3 3 2 1 1 оптимальное разбиение выглядит так: [1] [2 2] [3 3 3] [2] [1 1]. Эта задача несложно решается простым проходом по массиву (все одинаковые подряд идущие элементы помещаем в один подотрезок), но мы решим ее с помощью динамического программирования для примера.
 

	int n;
	cin >> n;

	// заполняем массив с 1-индексацией
	vector arr(n + 1);
	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	// изначально ставим +оо в значения дп
	vector dp(n + 1, 1000000000);

	// массив длины ноль разбивать не нужно, поэтому для него ответ 0
	dp[0] = 0;

	// считаем ответ для dp[i] по возрастанию i
	for (int i = 1; i <= n; i++) {
		// в текущий момент arr[i] - последний элемент, значит он будет самым правым числом в последнем подотрезке
		// переберем все варианты того, где этот последний подотрезок начинался
		for (int j = i; j > 0; j--) {
			if (arr[j] != arr[i]) {
				// если встретили элемент, который не равен последнему, то подотрезок будет содержать разные числа, а это не подходит по условию
				// продолжать уже нет смысла, т.к. сдвигая левую границу левее, этот элемент не пропадет, поэтому делаем break
				break;
			}

			// представляем, что последний подотрезок был [j;i]
			// значит надо взять оптимальное разбиение первых j-1 элементов и прибавить 1 (сам подотрезок  [j;i])
			dp[i] = min(dp[i], dp[j - 1] + 1);
		}
	}
	cout << dp[n];

Если элементы могут не принадлежать ни одному из подотрезков, то необходимо просто рассмотреть соответствующий вариант, как dp[i] = dp[i - 1]

Задача

В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили её порядковым номером в русском алфавите (А – 1, Б – 2, …, Я – 33), а пробел – нулем. 
Требуется по заданной последовательности цифр найти количество исходных сообщений, из которых она могла получиться.

Входные данные:
В первой строке содержится последовательность из не более чем 70 цифр.

Выходные данные:
Выведите одно число - количество возможных сообщений.

Пример:
 
Входные данные Выходные данные
1025 4



time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Python2
Комментарий учителя