Friday, September 9, 2011

CF #85

Problem C.
Notice that nxm <= 40, so min(n,m)<=6, suppose n<=6, at most 6 columns;
for each row, try 2^6 ways to put spiders.
use dp with memorization to solve(m,prev,mask), prev is the bitset of row[r-1], mask is the cells in previous row that not covered yet, they have to be covered by current row.

No comments:

Post a Comment