在n*n的方格中填入1*2的方块pascal,可以横着填,也可以竖着填,要求填满

Question

在n*n的方格中填入1*2的方块pascal,可以横着填,也可以竖着填,要求填满

Answer 1

您求的是方案数还是最大能够填的方块数?
方案数：
状压DP：设f[i,j]为前i行全部填满,第i+1行的状态为j的方案数,那么如果j状态可以转移给k状态,则f[i,j]->f[i+1,k].通常都用的这个办法.即按行DP.预处理出所有j->k的方案(可以通过搜索等方法),然后直接转移.
最大能够填的方块数：
网络流：
设格子内某个点的坐标为(x,y)
从原点向所有(x+y)为奇数的点连一条容量为1的边.
从所有(x+y)为奇数的点向四周{(x-1,y),(x+1,y),(x,y-1),(x,y+1)}一条容量为1的边.
从所有(x+y)为偶数的点向汇点连一条容量为1的边.
然后跑网络流算法.最大流即为结果.