SmartCoder's blog

DP with Bitmask
By SmartCoder, 13 years ago, In English

Hi to all,

I have learned dp and bitmask but i want to mix between them.
I want a simple tutorial about dp with bitmask and a simple  problem explain the basic idea and it would be useful if you provide me with DP with bitmask problems sorted by difficulty .
Hope to help me , thanks in advanced . 
  • Vote: I like it
  • +11
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
bitmasks are used as state basically, thats it. nothing special about it i guess.
→ Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
you can see this problem : https://sites.google.com/site/olimpous88/problems/spoj-6072-chocolate
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Finally i got the idea behind using bitmask with Dp as rng_57 said it's just used as state.

thanks you also olimpo your link is very useful .
I understood this with the help of this TC problem  from last SRM 522 
it's really helpful.
now i want to practice if any one know problems on  DP with Bitmask  please mention it.but please try to mention  if the problem  easy or medium or hard.
thanks in advanced.
→ Reply
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it

http://acm.timus.ru/problem.aspx?space=1&num=1152
http://acm.timus.ru/problem.aspx?space=1&num=1817

http://acm.sgu.ru/problem.php?contest=0&problem=527
http://acm.sgu.ru/problem.php?contest=0&problem=536

http://mirror.codeforces.com/problemset/problem/8/C
http://mirror.codeforces.com/problemset/problem/16/E
http://mirror.codeforces.com/problemset/problem/71/E

→ Reply