Розбір

Автор: Єгор Дубовік

Розробник: Ігор Баренблат

Визначимо $a \subset b$ — вираз, що означає, що $a$ $an d$ $b = a$ ( $a$ є «підмаскою» $b$ ). Тут $an d$ — побітове І.

Розв'язуватимемо задачу покроково.

Визначимо $D_{i}$ — $m$ -бітова маска, де $j$ -ий біт рівний $1$ , якщо місто з номером $i$ належить списку з номером $j$ , та $0$ в протилежному випадку.
Як порахувати $D$ ? Це домашнє завдання :)
Визначимо $c n t D_{i}$ — кількість таких $j$ , що $D_{j} = i$ .
Як порахувати $c n t D$ ? Це домашнє завдання :)
Визначимо $in t ersec t_{ma s k}$ — кількість авіашляхів, що можуть утворитися за використання будь-якого зі списків, що відповідають одиничним бітам $m$ -бітової маски $ma s k$ .
Як порахувати $in t ersec t$ ? $in t ersec t_{ma s k} =$ $(2 s u m _{ma s k \subset a} c n t D _{a})$ (Для того щоб швидко порахувати значення, використовуйте ідею super magic algo(описано нижче)).
Визначимо $u ni o n_{ma s k}$ — кількість авіашляхів, що будуть утворені за використання списків, що відповідають одиничним бітам $m$ -бітової маски $ma s k$ (помітимо, що це значення не залежить від порядку використання списків).
Як порахувати $u ni o n$ ? Посилаючись на формулу включень-виключень, отримуємо: $u ni o n_{ma s k} = s u m_{a \subset ma s k} ((- 1)^{bi t s (a) + 1} \cdot in t ersec t_{a})$ (Для того щоб швидко порахувати значення, використовуйте super magic algo(описано нижче)). Тут $bi t s (m)$ — кількість одиничних бітів маски $m$ .
Розв'язуватимемо задачу методом динамічного програмування. Визначимо $d p_{ma s k}$ — максимальна кількість грошових одиниць, які можна заробити, використавши списки, що відповідають одиничним бітам $m$ -бітової маски $ma s k$ у довільному порядку.
Як порахувати $d p$ ? $d p_{0} = 0$ . $d p_{ma s k} = max (d p_{ma s k}$ $_{x or}$ $_{2^{i}} + f (u ni o n_{ma s k} - u ni o n_{ma s k}$ $_{x or}$ $_{2^{i}}) \cdot r_{i})$ , де $i$ — номери одиничних бітів $m$ -бітової маски $ma s k$ . Тут $x or$ — побітове виключне АБО.
Відповіддю до задачі є $d p_{2^{m} - 1}$ .

/// super magic algo

Нехай задається масив $a$ розміру $2^{m}$ . Необхідно знайти значення масиву $b$ , де $b_{i} = s u m_{j \subset i} a_{j}$ .

Здійснимо $m$ ітерацій, де після ітерації з номером $i$ значенням $b [x]$ буде $\sum a [y]$ , таких що $x$ $an d$ $y = y$ , та починаючи з біта з номером $i$ біти чисел $x$ та $y$ збігаються (біти нумеруються з 0).

Очевидно, що перед першою ітерацією $b [x] = a [x]$ . На ітерації з номером $i$ перерахуємо $b [x]$ .

Якщо в числі x біт з номером $i$ рівний $0$ , то $b_{n e w} [x] = b [x]$ .

Якщо в числі x біт з номером $i$ рівний $1$ , то $b_{n e w} [x] = b [x] + b [x$ $x or$ $2^{i}]$ .

Отже, легко реалізувати цей алгоритм так:

for (int i=0;i<(1<<m);i++){
    b[i]=a[i];
}
for (int i=0;i<m;i++){
    for (int mask=0;mask<(1<<m);mask++){
        if (mask&(1<<i)){
            b[mask]+=b[mask^(1<<i)];
        }
    }
}

/// end of super magic algo

Складність $O (n \cdot m + m \cdot 2^{m})$ часу та $O (n + 2^{m})$ пам'яті.