| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Is it possible to calculate the following recurrences in $$$O(N*2^N)$$$.
1) $$$dp[mask] = min(dp[mask] , dp[m_1] + dp[m_2]);$$$
where $$$m_1|m_2 = mask$$$
2) $$$dp[mask] = min(dp[mask] , dp[m_1] + dp[m_2]);$$$
where $$$m_1 \oplus m_2 = mask$$$ and $$$m_1$$$ ,$$$m_2$$$ are subsets of mask.
Auto comment: topic has been updated by ASHWANTH_K (previous revision, new revision, compare).
Isn't the second one the same as the first one?
yeah somewhat
The second one requires m1 and m2 to be disjoint though?
First one is the same as Grouping ..
its $$$3^n$$$ in editorial