Статистика решения: 10,98% участников полностью решили задачу, 65,85% набрали 0 баллов.

Решение задачи:

Рассмотрим решение задачи с использованием динамического программирования. Для наглядности, рассмотрим алгоритм на исходном примере. Представим условие задачи в виде матрицы смежности a. Элемент a[j][i] будет равняться 0 или 1, причем равенство 1 означает что, из j месяца можно «попасть» в i, то есть производительность цеха в месяце j больше производительности в месяце i, и процент брака с точностью до одной десятой процента в месяце j меньше, чем в i. Матрица a выглядит следующим образом:

		i
		1	2	3	4	5	6	7	8	9	10
j	1	0	1	0	1	1	1	1	1	1	1
	2	0	0	0	1	1	1	0	0	1	1
	3	0	0	0	1	1	1	1	1	1	1
	4	0	0	0	0	1	0	0	0	0	0
	5	0	0	0	0	0	0	0	0	0	0
	6	0	0	0	0	0	0	0	0	0	0
	7	0	0	0	0	0	0	0	0	1	1
	8	0	0	0	0	0	0	0	0	1	1
	9	0	0	0	0	0	0	0	0	0	0
	10	0	0	0	0	0	0	0	0	0	0

По условию задачи будет использована только правая верхняя половина матрицы, так как должна сохраняться хронологическая последовательность месяцев. Введем еще одну ключевую матрицу d. Элементом d[i][k] будет являться количество вариантов, с помощью которых можно построить последовательность длины k, заканчивающуюся в i месяце. Рассмотрим алгоритм заполнения такой матрицы. Очевидно, что первая строка будет единичной, так как из одного месяца мы можем всегда сделать последовательность длины 1, заканчивающуюся в том же самом месяце. Далее начнем заполнять вторую строку:

• очевидно, что не существует последовательности длины 2, заканчивающейся в 1 месяце;

• последовательность длины 2, заканчивающуюся во втором месяце можно получить одним способом, так как последовательность длины 1 идущая ранее в хронологическом порядке только 1, а также из первого месяца можно «попасть» во второй;

• в третий месяц «попасть» нельзя ни из первого, ни из второго, поэтому таких последовательностей нет;

• в четвертый месяц можно «попасть» из всех трех предыдущих, поэтому будет 3 таких последовательности;

• и т.д.

Можно записать формулу, для вычисления d[i][k]:

 

Применительно к данному примеру, матрица d будет выглядеть следующим образом:

		i – последний месяц послед-ти
		1	2	3	4	5	6	7	8	9	10
k – длина послед-ти	1	1	1	1	1	1	1	1	1	1	1
	2		1	0	3	4	3	2	2	5	5
	3			0	1	4	1	0	0	5	5
	4				0	1	0	0	0	0	0
	5					0	0	0	0	0	0
	6						0	0	0	0	0
	7							0	0	0	0
	8								0	0	0
	9									0	0
	10										0

Для получения ответа остается найти первую ненулевую с конца строку, и сосчитать в этой строке сумму элементов. Приведенный алгоритм решает более широкую задачу – он позволяет найти не только количество вариантов с максимальным K, но и количество вариантов с любым K.

Заданы две последовательности чисел: объем продукции и процент брака. Требуется найти наибольшую подпоследовательность, в которой объем продукции растет, а процент брака падает.

10
313 100
313 106
442 106
442 104
475 104
475 102
539 102
539 109
682 109
682 111

5
32