Паркан для трави#1526

Паркан для трави (Розбір)

Площа трикутника зі сторонами $a, b, c$ a, b, c обчислюється у функції area за формулою Герона:

S = (p (p - a) (p - b) (p - c)), де p = (a + b + c) /2

S = \sqrt{(p (p - a)(p - b)(p - c))},~де~p = (a + b + c) / 2

Нехай $P$ — деяка підмножина наявних шматків огорожі. Функція FindSol( $ma s k$ ) знаходить максимальну площу, яку можна огородити за допомогою трикутників, складених із шматків цієї підмножини.

Змінна $ma s k$ представляє собою маску підмножини: це $16$ -бітове число, $i$ -ий біт якого дорівнює $1$ , якщо підмножина $P$ містить шматок $f e n ces [i]$ fences[i], і $0$ інакше.

Відповіддю на задачу буде значення FindSol( $2^{n} - 1)$ 2^n - 1), де $n$ — кількість чисел у масиві $f e n ces$ .

Значення всіх можливих масок $ma s k$ лежать в діапазоні від $0$ до $2^{16} - 1$ 2^{16} - 1 (оскільки за умовою є не більше $16$ шматків огорожі). У комірці $b es t [ma s k]$ best[mask] зберігається максимальна площа, яку можна огородити підмножиною шматків огорожі, відповідною масці $ma s k$ .

Для обчислення FindSol( $ma s k$ ) слід перебрати всі можливі трійки шматків огорожі $i, j, k$ i, j, k, які присутні в $ma s k$ . Для кожної трійки перевіряється нерівність трикутника, щоб переконатися, що з цих шматків можна скласти трикутник. Якщо трикутник можливий, обчислюється сума:

a r e a (f e n ces [i], f e n ces [j], f e n ces [k]) + F in d S o l (ma s k i, j, k)

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

Далі перебираються всі такі трійки $(i, j, k)$ (i, j, k), і вибирається та, для якої вказана сума максимальна. Це максимальне значення присвоюється комірці $b es t [ma s k]$ best[mask]:

F in d S o l (ma s k) = (i, j, k) \in ma s k 0 \leq i < j < k < n max (a r e a (f e n ces [i], f e n ces [j], f e n ces [k]) + F in d S o l (ma s k ∖ {i, j, k}))

FindSol(mask) = \max_{\substack{(i,j,k) \in mask \\ 0 \le i < j < k < n}} (area(fences[i], fences[j],fences[k]) + FindSol(mask \setminus \{i, j, k\}))

Якщо спочатку довжини шматків огорожі відсортувати, то при перевірці нерівності трикутника (сторони якого дорівнюють $f e n ces [i], f e n ces [j], f e n ces [k]$ fences[i], fences[j], fences[k]), достатньо перевірити тільки одну умову:

f e n ces [i] + f e n ces [j] > f e n ces [k]

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

Оскільки при сортуванні виконується нерівність

f e n ces [i] \leq f e n ces [j] \leq f e n ces [k],

fences[i] \le fences[j] \le fences[k],

з цього завжди слідує, що

f e n ces [i] + f e n ces [k] > f e n ces [j] і f e n ces [j] + f e n ces [k] > f e n ces [i] .

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

Приклад

У першому тесті оптимально побудувати трикутники зі сторонами $(4, 5, 6)$ (4, 5, 6) і $(7, 8, 9)$ (7, 8, 9). Сумарна огороджена площа в цьому випадку дорівнює $36.7544$ .

У другому тесті відповідь дорівнює $0$ , оскільки з огород неможливо скласти жодного трикутника.

У третьому тесті слід побудувати трикутник зі сторонами $(4, 4, 4)$ (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 повертає максимальну площу, яку можна огородити за допомогою трикутників, складених із оград, включених у маску $ma s k$ .

double FindSol(int mask)
{

Якщо значення в масиві $b es t [ma s k]$ best[mask] більше або дорівнює нулю, воно вже розраховане, і функція повертає це значення. Це дозволяє уникнути повторних обчислень і прискорює роботу алгоритму.

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

Ініціалізуємо $b es t [ma s k] = 0$ best[mask] = 0.

  best[mask] = 0;

Перебираємо всі можливі трійки індексів $(i, j, k)$ (i, j, k) таких, що відповідні огради включені в $ma s k$ .

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

Якщо трикутник існує, обчислюємо суму:

площа поточного трикутника $a r e a (f [i], f [j], f [k])$ area(f[i], f[j], f[k]);
плюс максимальна площа, яку можна огородити залишеними огородами, виключаючи використані в цій трійці:

F in d S o l (ma s k^(1 << i)^(1 << j)^(1 << k))

FindSol(mask~\hat{}~(1 << i)~\hat{}~(1 << j)~\hat{}~(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);

Ініціалізуємо масив $b es t$ .

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

Обчислюємо і виводимо відповідь.

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