Палички#1405

Палички (Розбір)

Нехай $S$ — даний набір паличок. Необхідно знайти два непересічних підмножини $A$ і $B$ з $S$ , такі, щоб палички кожного з них можна було розбити на дві підмножини з рівною сумою довжин.

Для кожного підмножини $ma s k \subseteq S$ mask \subseteq S обчислимо суму довжин його паличок і запишемо в $s u m [ma s k]$ sum[mask].

Переберемо всі підмножини $I \subset S$ I \subset S. Для кожної підмножини $I$ переберемо всі його підмножини $J \subset I$ J \subset I. Якщо існує таке $J$ , що $2 \cdot s u m [J] = s u m [I]$ 2 \cdot sum[J] = sum[I] (тобто сумарна довжина паличок в $J$ вдвічі менша від суми довжин усіх паличок з $I$ ), то підмножина $I$ можна використовувати в якості протилежних сторін прямокутника. У цьому випадку встановимо $c an [I] = t r u e$ can[I] = true.

Вся описана процедура виконується за $O (3^{n})$ O(3^n).

Переберемо всі підмножини множини паличок. Якщо для деякого множини $I$ існує підмножина $J \subset I$ J \subset I таке, що $c an [J] = t r u e$ can[J] = true і $c an [I x or J] = t r u e$ can[I~xor~J] = true (тобто множини $J$ і $I x or J$ I~xor~J не перетинаються), то тим самим отримуємо один з можливих розподілів паличок між горизонтальними і вертикальними сторонами прямокутника.

Довжини сторін такого прямокутника дорівнюють $s u m [J] /2$ sum[J] / 2 і $s u m [I x or J] /2$ sum[I~xor~J] / 2. Серед усіх знайдених варіантів обираємо прямокутник з максимальною площею.

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

Довжини паличок зберігаються в масиві $a$ . Для кожного підмножини паличок $ma s k$ зберігаємо їхню сумарну довжину в масиві $s u m [ma s k]$ sum[mask]. Значення $c an [ma s k]$ can[mask] встановлюємо в $t r u e$ , якщо множина $ma s k$ можна поділити на дві підмножини з рівною сумою довжин, які відповідатимуть протилежним сторонам прямокутника.

#define MAX 16
int a[MAX];
int sum[1 << MAX];
bool can[1 << MAX];

Основна частина програми. Читаємо вхідні дані.

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

Переберемо всі підмножини паличок і обчислимо сумарну довжину кожного з них.

for (i = 0; i < 1 << n; i++)
  for (j = 0; j < n; j++)
    if (i & (1 << j)) sum[i] += a[j];

Далі переберемо всі можливі підмножини множини паличок. Якщо для деякого множини $I$ існує підмножина $J \subset I$ J \subset I таке, що сумарна довжина паличок в $J$ вдвічі менша сумарної довжини паличок в $I$ , то встановимо $c an [I] = t r u e$ can[I] = true. У цьому випадку палички з множини $I$ можна використовувати як протилежні сторони прямокутника.

for (i = 1; i < 1 << n; i++) 
{
  int s = sum[i];
  for (j = i; j > 0; j = (j - 1) & i)
    if (sum[j] * 2 == s) 
    {
      can[i] = true;
      break;
    }
}

C++

Переберемо всі підмножини множини паличок. Якщо для деякого множини $I$ існує підмножина $J \subset I$ J \subset I таке, що $c an [J] = t r u e$ can[J] = true і $c an [I x or J] = t r u e$ can[I~xor~J] = true, то отримуємо один з можливих розподілів паличок між горизонтальними і вертикальними сторонами прямокутника. Довжини сторін такого прямокутника дорівнюють $s u m [J] /2$ sum[J] / 2 і $s u m [I x or J] /2$ sum[I xor J] / 2.

res = 0;
for (i = 1; i < 1 << n; i++)
  for (j = i; j > 0; j = (j - 1) & i)
    if (can[j] && can[i ^ j])
      res = max(res, sum[j] / 2 * 1LL * sum[i ^ j] / 2);

Виводимо площу знайденого прямокутника максимального розміру.

printf("%lld\n",res);