1526. Забор для травы

Возле виллы Пемберли, расположенной в южном районе Байтляндии, находится большое пастбище. Миссис Дарси беспокоится о своих нежных растениях, которые могут быть вытоптаны незнакомцами. Поэтому она решила оградить на пастбище некоторые участки земли треугольными заборами.

В подвале у миссис Дарси имеется несколько оград для забора. Каждую треугольную область она формирует, используя ровно три ограды, так что каждая сторона треугольника соответствует одной ограде. Ограды достаточно прочные и красивые, поэтому она не будет соединять несколько оград, чтобы получить одну сторону, или разрезать одну ограду на более короткие части. Цель миссис Дарси — оградить как можно большую суммарную площадь пастбища.

Вход. Каждая строка содержит отдельный тест. Первое число в строке – количество оград n (n ≤ 16), имеющихся у миссис Дарси. Далее следуют n целых чисел от 1 до 100 – длины этих оград.

Выход. Для каждого теста выведите в отдельной строке максимальную площадь, которую можно оградить с использованием имеющихся оград. Ответ необходимо вывести с точностью до 4 десятичных знаков.

Пример входа	Пример выхода
7 3 4 5 6 7 8 9 4 1 2 4 8 4 7 4 4 4	36.7544 0.0000 6.9282

РЕШЕНИЕ

динамическое программирование - маски

Анализ алгоритма

Площадь треугольника со сторонами a, b, c вычисляется в функции area по формуле Герона:

S = , где p =

Пусть P – некоторое подмножество имеющихся кусков забора. Функция FindSol(mask) находит максимальную площадь, которую можно оградить с помощью треугольников, составленных из кусков этого подмножества.

Переменная mask представляет собой маску подмножества: это 16-битовое число, i-ый бит которого равен 1, если подмножество P содержит кусок fences[i], и 0 иначе.

Ответом на задачу будет значение FindSol(2ⁿ – 1), где n – количество чисел в массиве fences.

Значения всех возможных масок mask лежат в диапазоне от 0 до 2¹⁶ – 1 (так как по условию имеется не более 16 кусков забора). В ячейке best[mask] хранится максимальная площадь, которую можно оградить подмножеством кусков забора, соответствующим маске mask.

Для вычисления FindSol(mask) следует перебрать все возможные тройки кусков забора i, j, k, которые присутствуют в mask. Для каждой тройки проверяется неравенство треугольника, чтобы убедиться, что из этих кусков можно составить треугольник. Если треугольник возможен, вычисляется сумма:

area(fences[i], fences[j], fences[k]) + FindSol(mask \ {i, j, k})

Далее перебираются все такие тройки (i, j, k), и выбирается та, для которой указанная сумма максимальна. Это максимальное значение присваивается ячейке best[mask]:

FindSol(mask) =

Если изначально длины кусков забора отсортировать, то при проверке неравенства треугольника (стороны которого равны fences[i], fences[j], fences[k]), достаточно проверить только одно условие:

fences[i] + fences[j] > fences[k]

Поскольку при сортировке выполняется неравенство

fences[i] £ fences[j] £ fences[k],

из этого всегда следует, что

fences[i] + fences[k] > fences[j] и fences[j] + fences[k] > fences[i].

Пример

В первом тесте оптимально построить треугольники со сторонами (4, 5, 6) и (7, 8, 9). Суммарная ограждённая площадь в этом случае равна 36.7544.

Во втором тесте ответ равен 0, так как из оград невозможно составить ни одного треугольника.

В третьем тесте следует построить треугольник со сторонами (4, 4, 4). Обратите внимание, что длины оград могут повторяться.

Реализация алгоритма

Объявим глобальные переменные.

#define MAX 16

double best[1<<MAX];

int f[MAX+1];

Функция area вычисляет площадь треугольника с помощью формулы Герона.

double area(int a, int b, int c)

{

double p = (a + b + c) / 2.0;

return sqrt(p * (p - a) * (p - b) * (p - c));

}

Функция FindSol возвращает максимальную площадь, которую можно оградить с помощью треугольников, составленных из оград, включённых в маску mask.

double FindSol(int mask)

{

Если значение в массиве best[mask] больше или равно нулю, оно уже рассчитано, и функция возвращает это значение. Это позволяет избежать повторных вычислений и ускоряет работу алгоритма.

if (best[mask] >= 0.0) return best[mask];

Инициализируем best[mask] = 0.

best[mask] = 0;

Перебираем все возможные тройки индексов (i, j, k) таких, что соответствующие ограды включены в mask.

for (int i = 0; i < n - 2; i++) if (mask & (1 << i))

for (int j = i + 1; j < n - 1; j++) if (mask & (1 << j))

for (int k = j + 1; k < n; k++) if (mask & (1 << k))

Проверяем условие существования треугольника. Так как ограды изначально отсортированы, этого условия достаточно, чтобы треугольник существовал.

if (f[i] + f[j] > f[k])

Если треугольник существует, вычисляем сумму:

· площадь текущего треугольника area(f[i], f[j], f[k]);

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

FindSol(mask ^ (1 << i) ^ (1 << j) ^ (1 << k))

best[mask] = max(best[mask], area(f[i],f[j],f[k]) +

FindSol(mask ^ (1 << i) ^ (1 << j) ^ (1 << k)));

return best[mask];

}

Основная часть программы. Читаем количество оград n.

while (scanf("%d",&n) == 1)

{

memset(f,0,sizeof(f));

Читаем длины оград и сортируем их по неубыванию.

for (i = 0; i < n; i++) scanf("%d",&f[i]);

sort(f,f + n);

Инициализируем массив best.

for (i = 0; i < (1 << MAX); i++) best[i] = -1.0;

Вычисляем и выводим ответ.

printf("%.4lf\n",FindSol((1 << n) - 1));

}