Необходимо спланировать выполнение 2n программ на n процессорах так, чтобы время завершения выполнения всех программ был

[Shved2298]

Как известно, большинство процессоров, которые сейчас выпускаются, являются многоядерными, то есть поддерживают выполнение нескольких инструкций одновременно. Компания Paraltel разработала новый тип двухъядерного процессора, который позволяет вмконувати 26 различных инструкций, которые обозначаются большими латинскими буквами. Выполнение каждой такой инструкции требует ровно одного такта работы процессора.

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

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

При выполнении двух программ на процессоре специальный управляющий устройство оптимизирует выполнение так, чтобы завершить выполнение обеих программ как можно раньше. Например, программы "ABB" и "ABC" можно выполнить на процессоре за 4 такта: сначала одновременно виконуютбся команды "A" обеих программ на разных ядрах, затем одновременно команды "B", затем команда "B" с первой программы и, наконец, "C" из второй. Аналогично, программы "CAB" и "BAB" выполняются за 4 такта.

Недавно специалисты компании собрали из n процессоров суперкомпьютер, на котором требуется выполнить 2n программ. Организация вычислений такая, что каждый процессор должен выконати ровно по две программы из этого набора, по одному на каждом ядре.

Вам необходимо спланировать выполнение 2n программ на n процессорах так, чтобы время завершения выполнения всех программ был минимальным.

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

В первой строке задано число n (1 ≤ n ≤ 10) — количество процессоров. Далее, в 2n строках заданы программы, которые необходимо выполнить. Каждая программа содержит от 1 до 100 команд. Каждая команда подается большой буквой.

Исходные данные

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

ПОМОГИТЕ ПОЖАЛУЙСТА, у меня есть алгоритм решения задачи, но я не могу все собрать в одну задачу и реализовать, если кто может помогите или подскажите как?ВОТ САМ АЛГОРИТМ:
Разобьем решение задачи на два этапа и рассмотрим каждый в отдельности.

Первым этапом будет построение графа. Вершинами его являются 2n программ, которые нам необходимо выполнить. Граф будет взвешенным, и вес ребра между двумя программами равен количеству времени, которое процессор потратит на их совместное выполнение. Это значение равно сумме длин программ минус те команды, которые будут выполняться одновременно. А таких команд не больше, чем LCS(a, b), где a и b — строки, описывающие программы, а LCS (Longest Common Subsequence, наибольшая общая подпоследовательность) — функция, находящая наибольшую общую подпоследовательность двух последовательностей.

В итоге функция нахождения веса ребра будет выглядеть следующим образом:

int dist(String a, String b) {
int[][] d = new int[a.length() + 1][b.length() + 1];
for (int[] ar : d) { Arrays.fill(ar, 1000000000); }
d[0][0] = 0;
for (int i = 0; i <= a.length(); ++i) {
for (int j = 0; j <= b.length(); ++j) {
if (i < a.length()) {
d[i + 1][j] = Math.min(d[i + 1][j], d[i][j] + 1);
}
if (j < b.length()) {
d[i][j + 1] = Math.min(d[i][j + 1], d[i][j] + 1);
}
if (i < a.length() && j < b.length() && a.charAt(i) == b.charAt(j)) {
d[i + 1][j + 1] = Math.min(d[i + 1][j + 1], d[i][j] + 1);
}
}
}
return d[a.length()][b.length()];
}


Вторым же этапом решения будет нахождение в этом графе совершенного паросочетания, в котором вес максимального ребра минимизирован. Одним из самых простых алгоритмов, решающих эту задачу и укладывающихся в ограничения по времени, является динамическое программирование, но уже по подмножествам. Пусть для каждого набора вершин размера не более, чем k, мы знаем ответ. В таком случае перебрав все такие наборы и добавив к каждому все возможные ребра, еще в нем не лежащие, мы сможем посчитать ответ для всех наборов размера не более, чем k + 2.

int[] d = new int[1 << (2 * n)];
Arrays.fill(d, 1000000000);
d[0] = 0;
for (int mask = 0; mask + 1 < 1 << (2 * n); ++mask) {
if (d[mask] == 1000000000) {
continue;
}
int i = 0;
while ((mask & (1 << i)) != 0) {
++i;
}
for (int j = i + 1; j < 2 * n; ++j) {
if ((mask & (1 << j)) == 0) {
d[mask | (1 << i) | (1 << j)] = Math.min(d[mask | (1 << i) | (1 << j)], Math.max(d[mask], dist[i][j]));
}
}
}