following images shows the problem statement


following images shows the problem statement


| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
| Название |
|---|



Simple submask dp problem.
Let's count
dp[mask].maskis an integer and it's i-th bit is gonna representate whether i-th skill is owned by Alice.dp[mask]will be equal to mininimum cost of books we need to use to get skill setmask.N <= 15somask <= 2^N < 33000.Let's say binary mask of the initial set of Alice's skills is
initMask. Then at start we setdp[initMask] = 0. All other dp values are gonna be equal to+INF. To calculate the dp, we are going to iterate through all the booksiand all the masksmask. Then ifbookMask[i]represents binary mask of i-th book, formula would be something like:dp[mask | bookMask[i]] = min(dp[mask | bookMask[i]], dp[mask] + bookCost[i]), where|is binaryOR. After all the dp's are calculated the answer is the smallestdp[mask]within allmasks that contain the set of skills we need to get. If the answer is greater or equal to infinity, that means that Alice can't get such set of skills.The time complexity is smth like
O(2^N * M)Got it!
Thanks