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

Автор motherofgod88, история, 7 лет назад, По-английски
  • Проголосовать: нравится
  • +55
  • Проголосовать: не нравится

Автор motherofgod88, история, 9 лет назад, По-английски

UPD: i found the problem here http://codeforces.me/problemset/gymProblem/100589/G

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.

Полный текст и комментарии »

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