$\quad$ 1. 所谓的状态压缩DP,就是用二进制数保存状态。为什么不直接用数组记录呢?因为用一个二进制数记录方便作位运算。前面做过的八皇后,八数码,也用到了状态压缩。
$\quad$ 2. 本题等价于找到所有横放 1 X 2 小方格的方案数,因为所有横放确定了,那么竖放方案是唯一的。
$\quad$ 3. 用f[i][j]记录第i列第j个状态。j状态位等于1表示上一列有横放格子,本列有格子捅出来。转移方程很简单,本列的每一个状态都由上列所有“合法”状态转移过来f[i][j] += f[i - 1][k]
$\quad$ 4. 两个转移条件: i 列和 i - 1列同一行不同时捅出来 ; 本列捅出来的状态j和上列捅出来的状态k求或,得到上列是否为奇数空行状态,奇数空行不转移。
$\quad$ 5. 初始化条件f[0][0] = 1,第0列只能是状态0,无任何格子捅出来。返回f[m][0]。第m + 1列不能有东西捅出来。
#include<bits/stdc++.h>
using namespace std;
const int N = 12, M = 1 << N;
int st[M];
long long f[N][M];
int main(){
int n, m;
while (cin >> n >> m && (n || m)){
for (int i = 0; i < 1 << n; i ++){
int cnt = 0;
st[i] = true;
for (int j = 0; j < n; j ++)
if (i >> j & 1){
if (cnt & 1) st[i] = false; // cnt 为当前已经存在多少个连续的0
cnt = 0;
}
else cnt ++;
if (cnt & 1) st[i] = false; // 扫完后要判断一下最后一段有多少个连续的0
}
memset(f, 0, sizeof f);
f[0][0] = 1;
for (int i = 1; i <= m; i ++)
for (int j = 0; j < 1 << n; j ++)
for (int k = 0; k < 1 << n; k ++)
if ((j & k) == 0 && (st[j | k]))
// j & k == 0 表示 i 列和 i - 1列同一行不同时捅出来
// st[j | k] == 1 表示 在 i 列状态 j, i - 1 列状态 k 的情况下是合法的.
f[i][j] += f[i - 1][k];
cout << f[m][0] << endl;
}
return 0;
}
为什么结果不是f[m+1][0]
对啊,i从1开始的,不应该是m+1嘛
为什么循环不直接从i=0开始
后面还有个i-1呢,你从0开始不就直接越界了
真正的列是从0~m-1,m是不存在的,但第m列可以保证前m-1都计算好了
// st[j | k] == 1 表示 在 i 列状态 j, i - 1 列状态 k 的情况下是合法的.
那我为什么改成st[j]&&st[k]是错的啊
为什么f[0][0] = 1
捅出来!
感觉说法好奇怪哈哈哈
自己的一些理解:
https://www.acwing.com/solution/content/239291/
Orz
这里的预处理的循环条件为什么是i<1<<n 而不是i<1<<m 啊
有没有大佬解答一下
n行m列,预处理那边是对所有的状态进行处理,所以只管n就好了,应该是这样?
状态是竖着的,所以肯定是1<<n啊
朴素写法就是这里没搞懂
// 扫完后要判断一下最后一段有多少个连续的0 最后一段是什么意思?
比方一种状态的二进制是100100111000,最后这三个0就是最后一段
感谢,我在别的帖子问有人回答过我了,这里发下我的理解,请指正:
思路听懂了,但是第一步预处理搞不懂
就是对状态j进行枚举, 当出现连续的段有奇数个0时就置为false
非常清晰
楼主写的太好了!!我也研究了一下,写了更详细的代码解释:
https://www.acwing.com/solution/content/28088/
大佬们有需要可以看一哈。
tql
i >> j & 1 是什么意思?
奥 是取每一位的状态, 状压 二进制
这个运算顺序是先算 j & 1吗?
你好,运算顺序是先算i>>j 这句话是求i的二进制表示法中的第j位,然后这一位再和 1相与,看这一位是不是1,如果是1,就返回true
为什么
f[1][1] = 1
,第0列可以放置横这的小方块,桶到第一列吗?可以的
另外f[1][1]不一定等于1,要看你n和m的值
好的,谢谢大佬!
st[j |k]这里有一列中的连续的0为偶数个,就可以吗?
是的,
j|k ==i
,i-1
列的k状态和i
列的j状态进行或运算, 将可以得到i列空格状态。我写了详细的题解,你可以看看
你自己题解里写的对的,但是你这句话评论错了,“将可以得到i-1列空格状态”
嗯嗯,谢谢大佬指正
秒哇,老哥。但是我还是不太理解预处理过程是怎样的,为什么要枚举 1 << M
应该是枚举
1<<n
, 是状态压缩dp的套路,每一列一共有2^n
个状态可以
谢谢大佬,这个题解写的特别详细
同样的思路用python写的,提示超时,哪位大佬可以优化一下???
为什么第一列不需要特判答案还是正确的??
这里要从
f[i][j]
的集合表示讲起, 状态表示f[i][j]
: 前i-1
列已经确定,且从第i-1
列伸出的小方格在第i
列的状态为j
的方案数。棋盘是从第0列开始,没有-1列,所以第0列状态为0。棋盘为空,这种状态记录为一种方案。
f[0][0] = 1;