Minor submask dp optimisation

Правка en1, от usernameson, 2021-11-25 08:42:59

Overview

Assume you are doing bitmask dp where each mask starts with a value and for every mask you want to add this value to all its submasks.

Example Type problem

You have an array $$$a$$$ and for each number $$$x$$$ in $$$[1,10^{6}]$$$ you want to know how many $$$a_{i}$$$ have the property $$$a_{i}$$$ & $$$x = x$$$.

Standard approach

You can use the standard submask iteration to do it in $$$O(3^n)$$$.

Slight speed up

You can speed this up slightly by using a lazy prop style technique. Remove a bit in the original mask

Теги dp, bitmask

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский usernameson 2021-11-25 09:13:01 1019 Tiny change: 'n\n~~~~~\nfor(int ma' -> 'n\n~~~~~\n for(int ma' (published)
en1 Английский usernameson 2021-11-25 08:42:59 624 Initial revision (saved to drafts)