I am stuck in the ELEVATOR problem in cses dp section. I tried to find the solution online but couldn`t find any reliable source. PROBLEM LINK — https://cses.fi/problemset/task/1653. It would be a great help if someone can explain the idea behind it.
See here: Competitive Programmer's Handbook pdf page 103-104
Thanks a lot.
I cant understand what the bit operations are doing. Can you explain them?
I solved in this way I have two fields DP and Moves
Moves[Mask] — the minimum number of elevator rides
DP[Mask] — Minimum Weight Sum of People for the last Move
We know that we have moves in the priority so the transitions were
newDp = (DP[mask ^ (1 << j)] + w[j]) % x
newMoves = (Moves[mask ^ (1 << j)] + (newDp > Dp[mask ^ (1 << j]))
It means that if newDp is bigger that x then new Move is added, and we change the Moves and DP, if Moves > newMoves or (newDp < DP and Moves = newMoves)
Thanks for the explanation.