Закон Джунглей говорит очень ясно, что
каждый волк, обзаводясь семьей, может покинуть свою Стаю. Но как только его
волчата подрастут и станут на ноги, он должен привести их на Совет Стаи,
который собирается обычно раз в месяц, во время полнолуния, и показать всем
другим волкам.
Отец Волк
подождал, пока его волчата подросли и начали понемногу бегать, и в одну из тех
ночей, когда собиралась Стая, повел волчат, Маугли и Мать Волчицу на Скалу
Совета. Это была вершина холма, усеянная большими валунами, за которыми могла
укрыться целая сотня волков. Акела, большой серый волк-одиночка, избранный
вожаком всей Стаи за силу и ловкость взывал со своей скалы:
— Закон вам
известен, Закон вам известен! Смотрите же, волки!
Отец Волк
вытолкнул на середину круга Лягушонка Маугли. Усевшись на землю, Маугли
засмеялся и стал играть палочками.
Задачу себе он
придумал достаточно простую – надо было из этих палочек сложить прямоугольник
максимальной площади, причём все палочки использовать не обязательно.
Вход. Первая строка содержит количество палочек n (1 ≤ n ≤ 16). Во второй строке записаны длины этих палочек –
натуральные числа в диапазоне от 1 до 108.
Выход. Вывести максимальную площадь прямоугольника, который
можно сложить из данного набора палочек, или число 0 если прямоугольник сложить не получится.
|
Пример
входа |
Пример
выхода |
|
8 7 1 5 2 3 2
4 5 |
49 |
РЕШЕНИЕ
динамическое
программирование - маски подмножеств
Пусть S –
имеющееся множество палочек. Необходимо найти два непересекающихся подмножества
A и B из S, палочки каждого из которых можно разбить на два равных по длине
подмножества.
Для каждого
подмножества mask ⊆ S найдем сумму
длин палочек в sum[mask].
Переберем все подмножества I Ì S всех множеств палочек. Для каждого подмножества I переберем
все его подмножества J Ì I. Если для
множества I имеется такое подмножество J Ì I, что 2 * sum[J] = sum[I] (суммарная длина палочек в J в два раза меньше суммарной
длины палочек в I), то подмножество палочек I можно использовать в качестве противоположных
сторон прямоугольника. Установим can[I] = true. Указанную
операцию можно совершить за O(3n).
Перебираем все подмножества всех множеств палочек. Если для
множества I имеется такое подмножество J Ì I, что can[J] = can[I xor J] = true (множества J
и I xor J являются непересекающимися), то получим одно из возможных
распределений палочек для горизонтальных и вертикальных сторон. Длины сторон
прямоугольника равны sum[J] / 2 и sum[I xor J] / 2. Среди всех таких возможных прямоугольников
находим прямоугольник с наибольшей площадью.
Длины палочек
храним в массиве а. Для подмножества mask
палочек суммарную их длину храним в sum[mask].
can[mask] установим в true, если множество
mask можно разбить на два одинаковых
по суммарной длине подмножества (им соответствуют противоположные стороны
прямоугольника).
#define MAX 16
int a[MAX];
int sum[1 << MAX];
bool can[1 << MAX];
Основная часть
программы. Читаем входные данные.
scanf("%d",&n);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
Перебираем все подмножества палочек, вычисляем суммарную
длину каждого подмножества.
for (i = 0; i < 1 << n; i++)
for (j = 0; j < n; j++)
if (i & (1 << j)) sum[i] +=
a[j];
Перебираем все подмножества всех множеств палочек. Если для
множества I палочек имеется такое подмножество J Ì I, что суммарная длина палочек в J в два раза меньше
суммарной длины палочек в I, то установим can[I] = true.
Подмножество палочек из I можно использовать в качестве противоположных сторон
прямоугольника.
for (i = 1; i < 1 << n; i++)
{
int s = sum[i];
for (j = i; j > 0; j = (j - 1) & i)
if (sum[j] * 2 == s)
{
can[i] = true;
break;
}
}
Перебираем все подмножества всех множеств палочек. Если для
множества I палочек имеется такое подмножество J Ì I , что can[J] = can[I xor J] = true, то получим одно из
возможных распределений палочек для горизонтальных и вертикальных сторон. Длины
сторон прямоугольника равны sum[j] /
2 и sum[i ^ j] / 2.
res = 0;
for (i = 1; i < 1 << n; i++)
for (j = i; j > 0; j = (j - 1) & i)
if (can[j] && can[i ^ j])
res = max(res, sum[j] / 2 * 1LL * sum[i ^ j] / 2);
Выводим площадь искомого прямоугольника.
printf("%lld\n",res);