permutation problems using bitmask

Правка en1, от motherofgod88, 2015-08-31 22:24:41

in many problems involving counting some permutations, we use state dp[mask][i] which denotes solution for subproblem where i is the last element used from a given array and the bits in mask variable are set if those values have been taken. i read somewhere that state in a DP solution should uniqely represent a subproblem. so in this case, how is this representation unique?

suppose array is 1, 2, 3, 4, 5, 6.

mask = 15(1111) and i = 4. this permutation is 1234. this will count the permutation where elements from index 1 to 4 have been taken and index 4 is the last element. but for permutation 1324 also, the state will be same. so how this state will give correct answer in such cases.

i remember seeing such a problem about counting permutations in CF GYM. but i cant find it now. it was solved using bitmask.

Теги bitmask, permutation, dp

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский motherofgod88 2015-08-31 22:33:22 86
en1 Английский motherofgod88 2015-08-31 22:24:41 863 Initial revision (published)