Матч 314, Забор для травы (GrasslandFencer)

Дивизион 2, Уровень 3; Дивизион 1, Уровень 2

У Миссис Данси имеются несколько частей изгороди. Она хочет при помощи них ограничиться максимальную площадь. При этом известно, что любая замкнутая изгородь должна иметь форму треугольника, каждая сторона которого равна одной из имеющихся частей. Резать части нельзя, каждая сторона треугольника должна состоять только из одной части изгороди.

Необходимо найти максимальную площадь участка, которую можно оградить треугольными формами.

Класс: GrasslandFencer

Метод: double maximalFencedArea(vector<int> fences)

Ограничения: fences содержит от 1 до 16 элементов, 1 £ fences [i] £ 100.

Вход. Целочисленный массив fences, содержащий длины имеющихся кусков забора.

Выход. Максимальная площадь, которую можно оградить треугольными формами.

Пример входа

fences

{3,4,5,6,7,8,9}

{1,2,4,8}

{7,4,4,4}

Пример выхода

36.754383146489694

0.0

6.928203230275509

РЕШЕНИЕ

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

Площадь треугольника со сторонами 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]. Извлечение из подмножеста mask i – го элемента эквивалентно выполнению операции исключающего или: mask ^ (1 << i).

Если изначально длины кусков забора отсортировать, то при проверке неравенства треугольника (стороны которого равны 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].

ПРОГРАММА

#include <cstdio>

#include <cmath>

#include <vector>

#include <algorithm>

using namespace std;

double best[1<<16];

int n;

vector<int> f;

class GrasslandFencer

{

public:

double FindSol(int mask)

{

int i, j, k;

double mx = 0;

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

if (!mask) return 0;

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

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

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

if (f[i] + f[j] > f[k]) mx = max(mx,area(f[i],f[j],f[k]) +

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

best[mask] = mx;

return mx;

}

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

{

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

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

}

double maximalFencedArea(vector<int> fences)

{

sort(fences.begin(),fences.end());

n = fences.size(); f = fences;

memset(best,-1,sizeof(best));

return FindSol((1<<n) - 1);

}

};