分析
我们可以只考虑摆横向的板块,给纵向的板块留足空间,这样就能够达到棋盘分割的要求。
对于i-1–i列这个位置的棋盘格,我们需要考虑的是从i-1–i中,每一行的是否在这两个中有一个板块。
我们将被横向板块从i-1到i占用用了的方格记为1否则就为0,并用十进制数j来表示这个状态,这样我们就确定了我们的状态的表示f[i][j]的定义,i表示i列中被从i-1到i被横向能以j方案占用格子的情况数目。
j的确定是和i-2到i-1这个板块是否被占用有关的,我们将i-1列的板块分布状态记为k,要使得i和i-1不冲突,i-1这列有的行要为空才使得i-1到i能够放得下,所以就是j和k的取值不能够冲突,j&k的值要为0.
这就是第一个假如说能够放进去的要求。
对于哪些不能横放的格子,就只能纵向的放,也就是说我们要求纵向空着的是偶数倍的格子才放的下。这样我们的问题就变成了j方案中0的个数的问题。就是中间有几个空格子。比如说1001就能够满足要求
所以我们的状态转移方程就是f[i][j]+=f[i-1][k];k对应的是i-1的状态,这里是需要枚举的,也就是说我们需要两重循环来契合k与j。
由于数据比较多我们可以实现预处理一下有哪些数字之间是有偶数个0的和有哪两个数是相互契合的。
1 | //state[i]表示数字i中是否有偶数个零 |
最后就是枚举可用的方案就可以了
1 | f[0][0]=1; |
完整代码
1 | #include <iostream> |
本文作者: jiangyuhao
本文链接: http://example.com/2022/04/17/%E8%92%99%E5%BE%B7%E9%87%8C%E5%AE%89%E7%9A%84%E6%A2%A6%E6%83%B3/
版权声明: 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处!