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(a, b, c) по формуле Герона:

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].

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

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

#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)

{

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

best[mask] = 0;

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]) best[mask] = max(best[mask],

area(f[i],f[j],f[k]) +

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

return best[mask];

}

Основная часть программы. После считывания длин оград сортируем их по неубыванию.

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

{

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

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

sort(f,f+n);

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

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

}