2411
poj 2411 状压dp入门题
Mondriaan's Dream Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 29096 Accepted: 15505 Description Squares and rectangles fascinated the f ......
POJ2411 Mondriaan's Dream(多米诺密铺问题)
不妨设 \(n, m\) 相等,常规的状压 DP 做法时间复杂度为 \(O(n * 2^n)\),但是可以通过套用公式使复杂度变为 \(O(n^2)\)。 具体地,用 \(1*2\) 的小长方形覆盖 \(n*m\) 的棋盘的方案数为 \[\Large \prod\limits_{j = 1}^{\l ......