Блог пользователя Or_ion

solution to this problem
Автор Or_ion, 2 года назад, По-английски

following images shows the problem statement

  • Проголосовать: нравится
  • -10
  • Проголосовать: не нравится

»
2 года назад, # |
← Rev. 2   Проголосовать: нравится +14 Проголосовать: не нравится

Simple submask dp problem.

Let's count dp[mask]. mask is 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 set mask. N <= 15 so mask <= 2^N < 33000.

Let's say binary mask of the initial set of Alice's skills is initMask. Then at start we set dp[initMask] = 0. All other dp values are gonna be equal to +INF. To calculate the dp, we are going to iterate through all the books i and all the masks mask. Then if bookMask[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 binary OR. After all the dp's are calculated the answer is the smallest dp[mask] within all masks 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)

→ Ответить