1526. Grassland Fence

There is a large grassland next to the villa Pemberley in the southern region of Byterland. Mrs. Darcy is afraid of her potted plants being trampled by strangers, so she decides to fence in some triangular areas in the grassland.

Mrs. Darcy has several fences in her basement. She will form each triangular area using exactly three fences, such that each side of the triangle is a single fence. Since the fences are beautifully decorated, she will not glue multiple fences together to form a single side, or split a single fence into multiple smaller fences. Her goal is to fence in as large an area as possible.

Input. Each line is a separate test case. The first number in the line is the amount n (n ≤ 16) of Mrs. Darcy's fences. Next n numbers are the lengths of these fences which are the integers between 1 and 100.

Output. For each test case print in a separate line the maximal area that can be fenced in with 4 digits after the decimal point.

Sample input	Sample output
7 3 4 5 6 7 8 9 4 1 2 4 8 4 7 4 4 4	36.7544 0.0000 6.9282

SOLUTION

dynamic programming - masks

Algorithm analysis

Find the area of a triangle with sides a, b, c in the function area(a, b, c) using Heron’s formula:

S = , where p =

Let P be a subset of the available fence pieces. Let the function FindSol(mask) finds the maximum area that can be enclosed with triangular shapes. The variable mask contains the mask of the subset: it is a 16-bit number, the i-th bit of which is 1 if the subset P contains the piece fences[i], and 0 otherwise. The answer to the problem in this case will be the value FindSol(2ⁿ – 1), where n is the number of integers in the array 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].

Algorithm realization

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

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

}