状压DP

字数统计: 10.3k   |   阅读时长≈ 45 分钟

状态压缩DP

1. 蒙德里安的梦想

推荐学习视频：E31 状态压缩DP 蒙德里安的梦想_bilibili，参考博客：AcWing 291. 蒙德里安的梦想 - AcWing

  • 思路：摆放方块时，先放横着的，再放竖着的（先把横着的放完最后用竖着的去填充），方案总数等于只放横着的小方块的合法方案数
  • 一定要理解下图的状态表示，每一行的状态 $1$ 表示：是横放的向下一列伸出；每一行的状态 $0$ 表示：状态 $1$ 的反集，竖放或由上一列伸出或未摆放
    • 对于图1
      • 第一列第一行是横放的向下一列伸出，故为1
      • 第一列第二行是竖放的，故为0
      • 第一列第三行是竖放的，故为0
      • 第一列第四含是横放的向下一列深处，故为1
    • 对于图2
      • 第二列第一行是由上一列伸出的，故为0
      • 第二列第二行是横放的向下一列伸出，故为1
      • 第二列第三行是横放的向下一列伸出，故为1
      • 第二列第四列是由上一列伸出的，故为0

image-20240427203142963

  • 状态表示： $f[i,j]$ 表示已经将前 $i-1$ 列摆好，且从第 $i-1$ 列伸出到第 $i$ 列，状态为 $j$ 时的方案数，比如图 $1$ 的 ${1\ 0\ 0\ 1}$ 转换为十进制就是 $9$ ，所以图 $1$ 表示的是 $f[1,9]$
  • 状态转移： $f[i-1,k]→f[i,j]$ ，$f[i,j]$ 可由上一列的多种可行状态转移而来，所以第二维坐标是 $k$ ，如下图中 ${0\ 0\ 1\ 1}$ 可以由 ${0\ 0\ 0\ 0}$ 或者 ${1\ 1\ 0\ 0}$ 转移而来

image-20240427203858461

  • 边界赋值：$f[0,0]=1$ 不摆是一种方案
  • 目标值：$f[m,0]$ 摆到第 $m$ 列且每一行都是 $0$，即刚好填满的状态

1.1. 状态预处理

  • 预处理即是检验在计算第 $i$ 行的状态 $j$ 时能否由第 $i-1$ 行的状态 $k$ 转换（是否合法），如果先进行了预处理的话那么在计算 $dp$ 数组的时候就很容易了

  • 我们引入合并列的状态表示

1.1.1. 合法状态

image-20240427210241200

  • 对于左图，第一列的状态是 $1,\ 1,\ 0,\ 0$，第二列的状态是 $0,\ 0,\ 1,\ 1$，二者做或运算得到的就是合并列的状态，为 $1,\ 1,\ 1,\ 1$，转换为十进制为 $15$，所以 $15$ 为合法状态
  • 对于右图，第一列的状态是 $1,\ 1,\ 0,\ 0$，第二列的状态是 $0,\ 0,\ 0,\ 0$，二者做或运算得到的就是合并列的状态，为 $1,\ 1,\ 0,\ 0$，转换为十进制为 $12$，所以 $12$ 为合法状态
  • 二者都为合法状态，当然合法状态不止这些
  • 为什么要做或运算？
  • 做或运算主要是为了检验有没有连续的奇数个 $0$，如果有连续的奇数个 $0$，表示按照这种规则摆放横方格，就没法对奇数个 $0$ 的位置摆竖方格。因为每一行上的数字为 $1$ 代表该行上的单元格是伸出的，为 $0$ 代表未伸出，若第 $i-1$ 列为 ${1,\ 1,\ 0,\ 0}$ 就代表第 $i-1$ 列每一行的伸出状态，第 $i$ 列为 ${0,\ 0,\ 1,\ 1}$ 代表第 $i$ 列的伸出状态，做或运算，是对这两列的每一行分别做或运算，如果对于某一行两列都为未伸出状态 $(0)$ 则合并后也为 $(0)$，出现偶数个相邻的 $0$ 可以用竖方格来填充，但是奇数个就没有办法了，所以出现连续奇数个 $0$ 是非法的！

1.1.2. 非法状态

image-20240427210636856

  • 对于左图，第一列的状态是 $1,\ 1,\ 0,\ 0$，第二列的状态是 $0,\ 0,\ -1,\ 1$（这里用 $-1$ 表示不摆放），二者做或运算得到的就是合并列的状态，为 $1,\ 1,\ 0,\ 1$，因为第三行没有空间竖放，转换为十进制为 $13$，所以 $13$ 为非法状态
  • 对于右图，第一列的状态是 $1,\ 1,\ 0,\ 0$，第二列的状态是 $0,\ 0,\ 1,\ -1$（这里用 $-1$ 表示不摆放），二者做或运算得到的就是合并列的状态，为 $1,\ 1,\ 1,\ 0$，因为第四行没有空间竖放，转换为十进制为 $14$，所以 $14$ 为非法状态
  • 二者都为非法状态，当然非法状态不止这些
  • 我们可以总结出，只要有连续的奇数个 $0$，就是竖放不了的，此时就是非法状态，除此以外就是合法状态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 预处理:判断合并列的状态i是否合法
// 如果合并列的某行是1表示横放,是0表示竖放
// 如果合并列不存在连续的奇数个0,即为合法状态
// 这里可以结合md文档来理解

// 枚举状态1~2^n-1,若n=4,有四行,则总状态数为15
for(int i=0;i<1<<n;i++) {
    st[i]=true;
    int cnt=0; // 连续0的个数
    // 枚举状态二进制表示的每一位,比如13=1101(2)
    // 依次枚举每一位,得到 1 1 0 1,这样就可以处理有多少个连续的0来判断是否合法
    for(int j=0;j<n;j++) {
        // 如果这一位是1,紧接着判断连续的0的个数是否是奇数
        if(i>>j &1) {
            if(cnt&1) {
                st[i]=false; // 这种状态不合法
                break;
            }
            // 该位是1可以把cnt清0了因为要的是连续的(但其实也可以不清零)
			cnt=0;
        } else {
            // 如果这位是0,那么cnt++
            cnt++;
        }
    }
    // 有可能最后一位是0,此时中间如果隔了个1,比如0100,那么连续的0的个数也出现了奇数
    // 那么也是非法的,处理高位0的个数
    if(cnt&1) st[i]=false;
}
// 输出每一种状态是否合法或者非法
for(int i=0;i<=1<<n;i++) {
    cout<<"st["<<i<<"]="<<st[i]<<endl;
}

1.2. 状态计算

  • 第一层状态枚举列，第二层状态枚举这一列的状态，第三层枚举上一列的状态，如果两列的状态兼容，则可以转移，何为兼容？
  1. 不出现重叠的 $1$：

image-20240427214132813

  • （虽然我觉得这张图的例子不恰当，因为这个状态本来就是非法的，但是也只有这张图了，假设它发生了吧）
  • 第一列的状态为 ${0,\ 0,\ 0,\ 1}$，第二列的状态为 ${0,\ 0,\ 1,\ 1}$，做且运算的结果是 ${0,\ 0,\ 0,\ 1}$ 不为 $0$，说明出现了重叠的 $1$
  • 为什么要做与运算？
  • 做或运算主要是为了检验有没有重叠的横方格，因为每一行上的数字为 $1$ 代表该行上的单元格是伸出的，为 $0$ 代表未伸出，若第 $i-1$ 列为 ${0,\ 0,\ 0,\ 1}$ 就代表第 $i-1$ 列每一行的伸出状态，第 $i$ 列为 ${0,\ 0,\ 1,\ 1}$ 代表第 $i$ 列的伸出状态，做与运算，是对这两列的每一行分别做与运算，如果对于某一行，如果两列都有伸出状态 $(1)$，则合并后也为 $(1)$，此时说明第 $i-1$ 列和第 $i$ 列在某一行上都向下一行伸出，此时横方块就重叠了，不合法！
  1. 不出现连续的奇数个 $0$

image-20240427214448929

  • 也就是我们预处理的时候预处理过的各种情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 状态转移
memset(f,0,sizeof f);
f[0][0]=1; // 第0列不摆放是一种合法方案
// 1) 枚举列
for(int i=1;i<=m;i++) {
    // 2)状态: 枚举第i列的状态
    for(int j=0;j<1<<n;j++) {
        // 3) 枚举第i-1列的状态
        for(int k=0;k<1<<n;k++) {
            // 两列状态兼容
            // 不出现重叠的1 且 不出现连续的奇数个0(前一列的状态和当前列做或运算)
            if((j&k)==0 && st[j|k]) {
                f[i][j]+=f[i-1][k]; // 前一列兼容状态的方案数之和
                printf("f[%d %d]=%d f[%d %d]=%d\n",i,j,f[i][j],i-1,k,f[i-1][k]);
            }
        }
    }
}
cout<<f[m][0]<<endl; // 第m列不横放,即下一列没有突出的,刚好放满,即答案

1.3. 完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=12+5; // 最大行数
const int M=1<<N; // 最大状态数
int n,m;
bool st[M]; // 总状态数
int f[N][M]; // 第i行共k个状态

int main() {
	// 同时为0时退出
	while(cin>>n>>m, n||m) {
		// 预处理:判断合并列的状态i是否合法
		// 如果合并列的某行是1表示横放,是0表示竖放
		// 如果合并列不存在连续的奇数个0,即为合法状态
		// 这里可以结合md文档来理解
		
		// 枚举状态1~2^n-1,若n=4,有四行,则总状态数为15
		for(int i=0;i<1<<n;i++) {
			st[i]=true;
			int cnt=0; // 连续0的个数
			// 枚举状态二进制表示的每一位,比如13=1101(2)
			// 依次枚举每一位,得到 1 1 0 1,这样就可以处理有多少个连续的0来判断是否合法
			for(int j=0;j<n;j++) {
				// 如果这一位是1,紧接着判断连续的0的个数是否是奇数
				if(i>>j &1) {
					if(cnt&1) {
						st[i]=false; // 这种状态不合法
						break;
					}
                    // 该位是1可以把cnt清0了因为要的是连续的(但其实也可以不清零)
					cnt=0;
				} else {
					// 如果这位是0,那么cnt++
					cnt++;
				}
			}
			// 有可能最后一位是0,此时中间如果隔了个1,比如0100,那么连续的0的个数也出现了奇数
			// 那么也是非法的,处理高位0的个数
			if(cnt&1) st[i]=false;
		}
		// 输出每一种状态是否合法或者非法
		for(int i=0;i<=1<<n;i++) {
			cout<<"st["<<i<<"]="<<st[i]<<endl;
		}

		// 状态转移
		memset(f,0,sizeof f);
		f[0][0]=1; // 第0列不摆放是一种合法方案
		// 1) 枚举列
		for(int i=1;i<=m;i++) {
			// 2)状态: 枚举第i列的状态
			for(int j=0;j<1<<n;j++) {
				// 3) 枚举第i-1列的状态
				for(int k=0;k<1<<n;k++) {
					// 两列状态兼容
					// 不出现重叠的1 且 不出现连续的奇数个0(前一列的状态和当前列做或运算)
					if((j&k)==0 && st[j|k]) {
						f[i][j]+=f[i-1][k]; // 前一列兼容状态的方案数之和
						printf("f[%d %d]=%d f[%d %d]=%d\n",i,j,f[i][j],i-1,k,f[i-1][k]);
					}
				}
			}
		}
		cout<<f[m][0]<<endl; // 第m列不横放,即下一列没有突出的,刚好放满,即答案
	}
	return 0;
}

2. 小国王

推荐学习视频：E25 状态压缩DP 小国王_bilibili
题目描述：在 $n×n$ 的棋盘上放 $k$ 个国王，国王可以攻击相邻的 $8$ 个格子，求使他们无法互相攻击的方案总数

  • 比如在一个 $3×3$ 的矩阵中放 $2$ 个国王，一共有 $16$ 种方案
  • 我们可以用二维数组表示一行上国王的放置情况，比如某一行为 $[1,\ 0,\ 1]$ 就表示第一列和第三列上有国王，但是当 $n$ 偏大时就会浪费掉很多空间甚至 $MLE$，所以将 $[1,\ 0,\ 1]$ 当作二进制数，转换成十进制数 $5$ 来表示状态
  • 所谓状态压缩即为
    • 用二进制表示状态
    • 用十进制存储状态

image-20240501224207803

2.1. 状态预处理

  • 假设 $n$ 的值就为 $3$，那么对于一个 $3×3$ 的棋盘，每一行的所有状态有 $2^3=8$ 种，即 $000,\ 001,\ 010,\ 011,\ 100,\ 101,\ 102,\ 110,\ 111$

2.1.0. 数据结构

1
2
3
4
5
6
7
const int N=12+5;
int n,k; // 行数,国王个数
int cnt; // 同一行的合法状态个数
int s[1<<12]; // 同一行的合法状态集
int num[1<<12]; // 每个合法状态包含的国王数
ll f[12][144][1<<12]; // 最大12行,国王个数最大12×12,1左移12位表示所有状态最大值
// f[i,j,a]:前i行放了j个国王,第i行第a个状态时的方案

2.1.1. 行内合法

  • 因为国王会攻击相邻 $8$ 个位置（同一行、同一列、两条对角线的首个元素），所以同一行不能存在两个相邻的 $1$，每行的合法状态只剩：$000,\ 001,\ 010,\ 100,\ 101$
  • 用位运算 $!(i\ &\ i>>1)$ 实现，即把 $i$ 和右移一位的 $i$ 按位相与，如果两位同为 $1$ 相与之后的结果为 $1$，此时说明存在两个相邻的 $1$

image-20240501231046905

  • 代码上每次枚举每一行的所有状态，如果行间不相邻则合法，合法时依次提取这个合法状态的每一位，统计有多少个 $1$，即出现了多少个国王，最后保存到 $s$ 和 $num$ 数组中去
1
2
3
4
5
6
7
8
9
10
11
12
13
cin>>n>>k;
// 预处理
for(int i=0;i<(1<<n);i++) {
    // 枚举一行的所有状态(n个国王,共2^n-1状态)
    if(!(i&i>>1)) {
        // 不存在相邻的1,则为合法状态
        s[cnt++]=i; // s即为每一行的合法状态集,这里记录一下,cnt++
        // i为合法状态才进入这个if
        // 每次右移j位(j从0到n-1)就可以取到i的每一位,&1 即可判断1的个数
        for(int j=0;j<n;j++) 
            num[i]+=(i>>j&1); // 每个合法状态的1的个数,
    }
}

2.1.2. 行间兼容

  • 行内只用考虑行，行间还需要考虑对角线，即对第 $i$ 行考虑 $i-1$ 行的左上角、正上方和右上方三个位置，所以行 $a$ 对行 $b$ 考虑与 $b$ 直接相与（正上方）、右移（左上方）、左移（右上方）按位相与是否出现 $1$（是否相邻）
  • 在状态计算时进行行间兼容的判断

image-20240501231306824

2.2. 状态计算

  • 状态表示：$f[i,j,a]$ 表示前 $i$ 行已经放了 $j$ 个国王，第 $i$ 行的第 $a$ 个状态的方案数

  • 状态转移：$f[i,j,a]=\sum\ f[i-1,j-c[a],b]$ 表示来自上一行 $i-1$ 行，第 $i$ 行已经放了 $a$ 状态时（已经有几个国王）【用前 $i$ 行已经放的国王个数 $j$ 减去第 $i-1$ 行放的国王个数 $c[a]$】，再从上一行中所有的能和 $a$ 状态兼容的状态中累加求和，即是说，我们遍历到第 $i$ 行时，遍历第 $i$ 行的所有自己行内合法的状态，对每一个状态与上一行 $i-1$ 间处理行间兼容，如果兼容则加 $1$，相当于一个累加求和的过程

  • 目标值：$ans=\sum\ f[n,k,a]$，前 $n$ 行中已经放了 $k$ 个国王，对所有的第 $n$ 行的合法状态进行累加求和

image-20240501232626218

  • 代码上

  1. 每一行可以不放国王最多 $k$ 个国王，所以枚举国王范围是 $[0,k]$

  2. 为什么特判 $j>=c$ ？控制 $f[i-1][j-c][b]$ 中的下标不为负数，表示可以继续放国王

  3. 为什么枚举行数要从 $[1,n]$ 呢？因为我们输出的目标值是 $f[n+1][k][0]$ 即遍历到了 $f[n][k][cnt-1]$ 的下一个状态，相当于第 $n+1$ 行什么都不放，两个状态等价，下面两段代码是等价的，好好理解，说实话这里我也没太明白，关于这部分的讲解从视频的 $17:25$ 开始

image-20240501235708410

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 状态计算
f[0][0][0]=1; // 不放国王是一种方案
// 1) 枚举行
for(int i=1;i<=n+1;i++) {
    // 2) 枚举国王数
    for(int j=0;j<=k;j++) {
        // 3) 枚举第i行的合法状态
        for(int a=0;a<cnt;a++) {
            // 4) 枚举第i-1行的合法状态
            for(int b=0;b<cnt;b++) {
                int c=num[s[a]]; // 第i行第a个合法状态的国王数
                // 可以继续放国王,不存在同列和斜对角的1
                if((j>=c) && !(s[b]&s[a]) && !(s[b]&(s[a]<<1)) && !(s[b]&(s[a]>>1))) {
                    f[i][j][a]+=f[i-1][j-c][b]; // 从第i-1行向第i行转移
                }
            }
        }
    }
}
cout<<f[n+1][k][0]; // 第n+1行什么都不,只在1~n行放国王

2.3. 完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=12+5;
int n,k; // 行数,国王个数
int cnt; // 同一行的合法状态个数
int s[1<<12]; // 同一行的合法状态集
int num[1<<12]; // 每个合法状态包含的国王数
ll f[12][144][1<<12]; // 最大12行,国王个数最大12×12,1左移12位表示所有状态最大值
// f[i,j,a]:前i行放了j个国王,第i行第a个状态时的方案

int main() {
	cin>>n>>k;
	// 预处理
	for(int i=0;i<(1<<n);i++) {
		// 枚举一行的所有状态(n个国王,共2^n-1状态)
		if(!(i&i>>1)) {
			// 不存在相邻的1,则为合法状态
			s[cnt++]=i; // s即为每一行的合法状态集,这里记录一下,cnt++
			// i为合法状态才进入这个if
			// 每次右移j位(j从0到n-1)就可以取到i的每一位,&1 即可判断1的个数
			for(int j=0;j<n;j++) 
				num[i]+=(i>>j&1); // 每个合法状态的1的个数,
		}
	}
	// 状态计算
	f[0][0][0]=1; // 不放国王是一种方案
	// 1) 枚举行
	for(int i=1;i<=n+1;i++) {
		// 2) 枚举国王数
		for(int j=0;j<=k;j++) {
			// 3) 枚举第i行的合法状态
			for(int a=0;a<cnt;a++) {
				// 4) 枚举第i-1行的合法状态
				for(int b=0;b<cnt;b++) {
					int c=num[s[a]]; // 第i行第a个合法状态的国王数
					// 可以继续放国王,不存在同列和斜对角的1
					if((j>=c) && !(s[b]&s[a]) && !(s[b]&(s[a]<<1)) && !(s[b]&(s[a]>>1))) {
						f[i][j][a]+=f[i-1][j-c][b]; // 从第i-1行向第i行转移
					}
				}
			}
		}
	}
	cout<<f[n+1][k][0]; // 第n+1行什么都不,只在1~n行放国王
	return 0;
}

3. 玉米田

推荐学习视频：E26 状态压缩DP 玉米田_bilibili
题目描述：玉米田的大小为 $n×m$，相邻土地不能同时种植玉米（种玉米的方格边缘不相交），部分土地不育无法种植玉米，求种植方案总数

  • 比如当玉米田大小为 $2×3$ 时，有下图 $8$ 种种植方案，其中红色的 $0$ 表示不育的土地

image-20240502123107098

  • 和上一题类似用二进制表示每一行的状态，再转换为十进制数存储状态，用一维数组存储

3.1. 状态预处理

  • 和上一题类似，从行内合法和行内兼容来考虑，本题的“相邻”指的是上下左右四个方向的位置

3.1.0. 数据结构

1
2
3
4
5
6
7
const int Mod=1e9;
int n,m; // 玉米田行数列数
int g[14]; // 各行的状态值
int cnt; // 同一行的合法状态个数
int s[1<<14]; // 一行的合法状态集
int f[14][1<<14];
// f[i,a]:已种植前i行,第i行第a个状态时的方案数

3.1.1. 行内合法

  • 若本行状态合法，则一定没有相邻的 $1$

image-20240502123651504

3.1.2. 行间兼容

  • 除了考察正上方的元素，本题相较于小国王多了一个地图，所以需要考察是否能种
  • 比如第 $i$ 行的地图为 $[1,1,0]$，每一行的合法状态有五个，他们没有相邻的 $1$，分别为：$[0,0,0],\ [0,0,1],\ [0,1,0],\ [1,0,0],\ [1,0,1]$，因为 $[0,0,1],\ [1,0,1]$ 与 $[1,1,0]$ 相与的结果不为本身（即出现了不能种的情况），所以合法状态还剩三个；此时还需要考察与上一行之间是否满足不相邻，比如遍历到 $a$ 行的第 $[0,1,0]$ 状态时，满足与此状态不相邻的有 $[0,0,0],\ [0,0,1],\ [1,0,0],\ [1,0,1]$ 共 $4$ 个

image-20240502124050540

3.1.3. 代码

  • 地图数组 $g$ 存储的是每一行二进制地图状态的十进制表示数，如某一行的状态是 $[1,1,0]$，则十进制状态为 $6$，至于如何用代码实现就是一种技巧了，$g[i]=(g[i]<<1)+x$，每次左移 $×2$ 提权随后加上这一位的值 $x$
  • 保存行内合法的方法与小国王一致，这里不阐释
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
cin>>n>>m;
// 预处理
for(int i=1;i<=n;i++) {
    for(int j=1;j<=m;j++) {
        int x;cin>>x;
        g[i]=(g[i]<<1)+x; // 保存各行的状态值
        // 模拟跟踪一下,g每次左移+x,得到的是第i行二进制状态的十进制数数值
        printf("g[%d]=%d\n",i,g[i]);
    }	
}
// 枚举一行的所有状态
for(int i=0;i<(1<<m);i++) {
    // 如果不存在相邻的1
    if(!(i&i>>1)) {
        s[cnt++]=i; // 保存合法状态的十进制表示数
    }
}

3.2. 状态计算

  • 状态表示：$f[i,a]$ 表示已经种植前 $i$ 行，第 $i$ 行第 $a$ 个状态时的方案数
  • 状态计算：$f[i,a]=\sum\ f[i-1,b]$（通过上一行所有的与第 $a$ 行兼容的状态进行累加求和）
  • 目标值：$ans=\sum\ f[n,a]$，即 $f[n+1,0]$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 状态计算
f[0][0]=1; // 题目说什么都不种是一种状态
// 1) 枚举行技巧
for(int i=1;i<=n+1;i++) {
    // 2) 枚举第i行合法状态
    for(int a=0;a<cnt;a++) {
        // 3) 枚举第i-1行合法状态
        for(int b=0;b<cnt;b++) {
            // a种在肥沃土地上,a b同列不同时为1
            if((s[a]&g[i])==s[a] && !(s[a]&s[b])) {
                f[i][a]=(f[i][a]+f[i-1][b])%Mod;
                // 模拟跟踪
                printf("f[%d %d]=%d f[%d %d]=%d\n",i,a,f[i][a],i-1,b,f[i-1][b]);
            }	
        }
    }
}
cout<<f[n+1][0]; // 第n+1行什么都不种
return 0;
  • 同时我们可以对状态转移的条件判断做一个加强，我们让 $a,b$ 两行的状态都种在肥沃土地上，上面代码的写法只判断了 $a$ 要种在肥沃土地上，但是上一行 $b$ 的五种合法状态中也可以排除一些与上一行的土地 $g[i-1]$ 相与结果不为本身的，这样转移次数就会变少
1
2
3
4
5
if((s[a]&g[i])==s[a] && (s[b]&g[i-1])==s[b] && !(s[a]&s[b])) {
    f[i][a]=(f[i][a]+f[i-1][b])%Mod;
    // 模拟跟踪
    printf("f[%d %d]=%d f[%d %d]=%d\n",i,a,f[i][a],i-1,b,f[i-1][b]);
}
  • 还可以这样写，过滤掉不合法状态，再累加求和
1
2
3
4
// 也可以这样写
// 过滤掉 a b 种在不育土地上,a b同列同时为1
if(s[a]&~g[i] || s[b]&~g[i-1] || s[a]&s[b]) continue;
f[i][a]=(f[i][a]+f[i-1][b])%Mod;

3.3. 完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=14+5;
const int Mod=1e9;
int n,m; // 玉米田行数列数
int g[14]; // 各行的状态值
int cnt; // 同一行的合法状态个数
int s[1<<14]; // 一行的合法状态集
int f[14][1<<14];
// f[i,a]:已种植前i行,第i行第a个状态时的方案数

int main() {
	cin>>n>>m;
	// 预处理
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			int x;cin>>x;
			g[i]=(g[i]<<1)+x; // 保存各行的状态值
			// 模拟跟踪一下,g每次左移+x,得到的是第i行二进制状态的十进制数数值
			printf("g[%d]=%d\n",i,g[i]);
		}	
	}
	// 枚举一行的所有状态
	for(int i=0;i<(1<<m);i++) {
		// 如果不存在相邻的1
		if(!(i&i>>1)) {
			s[cnt++]=i; // 保存合法状态的十进制表示数
		}
	}
	// 状态计算
	f[0][0]=1; // 题目说什么都不种是一种状态
	// 1) 枚举行技巧
	for(int i=1;i<=n+1;i++) {
		// 2) 枚举第i行合法状态
		for(int a=0;a<cnt;a++) {
			// 3) 枚举第i-1行合法状态
			for(int b=0;b<cnt;b++) {
				// a种在肥沃土地上,a b同列不同时为1
				if((s[a]&g[i])==s[a] && !(s[a]&s[b])) {
					f[i][a]=(f[i][a]+f[i-1][b])%Mod;
					// 模拟跟踪
					printf("f[%d %d]=%d f[%d %d]=%d\n",i,a,f[i][a],i-1,b,f[i-1][b]);
				}
				// 状态转移增强,让上一行b也必须种在肥沃土地上
//				if((s[a]&g[i])==s[a] && (s[b]&g[i-1])==s[b] && !(s[a]&s[b])) {
//					f[i][a]=(f[i][a]+f[i-1][b])%Mod;
//					// 模拟跟踪
//					printf("f[%d %d]=%d f[%d %d]=%d\n",i,a,f[i][a],i-1,b,f[i-1][b]);
//				}
				// 也可以这样写
				// 过滤掉 a b 种在不育土地上,a b同列同时为1
//				if(s[a]&~g[i] || s[b]&~g[i-1] || s[a]&s[b]) continue;
//				f[i][a]=(f[i][a]+f[i-1][b])%Mod;
			}
		}
	}
	cout<<f[n+1][0]; // 第n+1行什么都不种
	return 0;
}

/*
输入样例:
2 3
1 1 0
0 1 1
输出样例:
8
 */

4. 炮兵阵地

推荐学习视频：E27 状态压缩DP 炮兵部队_bilibili
题目描述：$n×m$ 的网格地图由平原和山地构成，炮兵只能放在平原，放在平原后攻击范围为横向左右各两格、纵向上下各两格，攻击范围不受地形影响，现在问在保证任意两支炮兵不互相攻击的前提下，在整个地图区域最多能摆放多少炮兵部队？

  • 和玉米田一样的是，不是所有的方格都能放，那么区别在哪里？

    • 横向和纵向上分别延申了两格，那么行内兼容和行间兼容的条件都会发生变化
    • 求的是最多能摆放多少部队，而不是总方案数

  • 同样的把每一行的地图用二进制表示，十进制存储，如 $PHHP→1001→9$（$P$ 表示平原，$H$ 表示山地）

4.1. 状态预处理

  • 横向和纵向上分别延申两格

4.1.0. 数据结构

1
2
3
4
5
6
7
8
9
const int N=110; // 最大行数
const int M=1<<10; // 列数最大为10,则状态最大有2^10-1
int n,m;
int g[N]; // 地图各行十进制表示数值
int cnt; // 每行合法状态个数
int s[M]; // 同一行的合法状态集个数
int num[M]; // 每个合法状态包含1的个数
int f[N][M][M]; // 110*1024*1024*4=440MB(int型4字节)
// f[i][a][b]:已放好前i行,第i行第a个状态,第i-1行第b个状态时能放置的最大数量

4.1.1. 行内合法

  • 若列数 $m=4$，则一行的所有状态有：$[0000,1111]$ 共 $15$ 个状态，合法即：不出现相邻的 $1$ 或不出现 $101$
  • 判断条件：$if(!(i&i>>1)\ &&\ !(i&i>>2))$ 为$true$，则 $i$ 合法
    • 若 $i=3,\ 0011$，$i>>1\ =\ 0001$，$0011&0001=0001$，取反为 $false$，所以 $i=3$ 不合法
    • 若 $i=5,\ 0101$，$i>>2\ =\ 0001$，$0101&0001=0001$，取反为 $false$，所以 $i=5$ 不合法

image-20240503101107406

4.1.2. 行间兼容

  • 现在用 $a$ 表示当前行，用 $b$ 表示上一行，用 $c$ 表示上上行，那么每遍历一个 $a$ 的合法状态并且 $a$ 与地图适配，$1$ 出现的位置都在平原上，那么再而去遍历 $b$ 的合法状态且不与 $a$ 有同列的冲突，确定好 $b$ 后再而去确定 $c$ 的状态，同理 $c$ 也不能和 $a$、$b$ 有同列冲突，这样就判定了一个合法状态

image-20240503101731400

4.1.3. 代码

  • 需要学习的技巧在于
    • 若输入的地图是字符类型的，如何把其当成二进制数并转换成十进制数存储起来
    • 考察相邻的 $11$ 的代码是 $!(i&i>>1)$，考察 $101$ 的代码是 $!(i&i>>2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
cin>>n>>m;
// 预处理地图
for(int i=1;i<=n;i++) {
    for(int j=0;j<m;j++) {
        char c;cin>>c;
        // 这个技巧很重要,如果是平原(即1)需要转换成二进制
        // m-j-1 是1需要偏移的长度,即出现在第几位,转换成二进制是多少
        if(c=='P') g[i]+=1<<(m-j-1); // 保存地图各行数值
    }
    printf("g[%d]=%d\n",i,g[i]);
}
// 预处理合法状态和1的个数
// 枚举一行的所有状态
for(int i=0;i<(1<<m);i++) {
    // 如果不存在11或101
    if(!(i&i>>1) && !(i&i>>2)) {
        s[cnt++]=i; // 保存这个合法状态
        // 统计这个合法状态包含1的个数,存进num
        for(int j=0;j<m;j++) {
            num[i]+=(i>>j&1); // j&1说明i偏移j位后末尾是1
        }
    }
}
// 打印所有合法状态看看
cout<<"输出合法状态:>"<<endl;
for(int i=0;i<cnt;i++) {
    printf("s[%d]=%d num[%d]=%d\n",i,s[i],i,num[i]);
}

4.2. 状态计算

  • 状态表示：$f[i,a,b]$ 表示已摆放前 $i$ 行，当前第 $i$ 行的状态为 $a$，并且第 $i-1$ 行的状态为 $b$ 时能摆放的最大数量（比玉米田多了一维来锁定第 $i-1$ 行的状态，注意这里不是方案数！）【为什么不再来一维表示第 $i-2$ 行的状态？因为状态转移时，$f[i,a,b]$ 是由 $f[i-1,b,c]$ 转移来的，即状态 $i$ 的上一行是状态 $i-1$ 的本行，在循环计算时 $c$ 也包含在内了】

  • 状态转移：$f[i,a,b]=max(f[i,a,b],f[i-1,b,c]+num[a])$ 是由上一个状态的最大数量加上当前行第 $a$ 行所能摆放炮兵的数量转移得到

  • 边界初值：$f[]=0$

  • 目标值：$ans=max(f[n,a,b])$，即 $f[n+2,0,0]$（多算两行，最后两行什么都不放）或从 摆放了前 $n$ 的各个状态中遍历求得最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 状态计算
// 1) 枚举行,多算两行,技巧同上
// 直接输出f[n+2][0][0] 这样就不用枚举最后一行n的所有合法状态挑出最大值
for(int i=1;i<=n+2;i++) {
    // 2) 枚举第i行合法状态
    for(int a=0;a<cnt;a++) {
        // 3) 枚举第i-1行合法状态
        for(int b=0;b<cnt;b++) {
            // 4) 枚举第i-2行合法状态
            for(int c=0;c<cnt;c++) {
                // 状态转移的条件
                if(!(s[a]&s[b]) && !(s[a]&s[c]) && !(s[b]&s[c]) // 任意两行不同列 
                   && (g[i]&s[a])==s[a] && (g[i-1]&s[b])==s[b]) // 地图适配a,地图适配b
                {
                    // s[a]: 状态a的十进制表示,num[s[a]]: 取出本行状态为a时这一行的炮兵个数
                    f[i][a][b]=max(f[i][a][b],f[i-1][b][c]+num[s[a]]);

                    // 模拟跟踪状态转移过程
                    printf("f[%d %d %d]=%d 由上一行 f[%d %d %d]=%d 加上本行炮兵个数 %d 转移而来\n",
                           i,a,b,f[i][a][b],i-1,b,c,f[i-1][b][c],num[s[a]]);
                }
            }
        }
    }
}
cout<<f[n+2][0][0]<<endl; // 等价于枚举第n行a/b所有状态遍历得到的最大值

4.3. 完整代码

模拟跟踪过程从视频 $17:35$ 开始

image-20240503114304814

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=110; // 最大行数
const int M=1<<10; // 列数最大为10,则状态最大有2^10-1
int n,m;
int g[N]; // 地图各行十进制表示数值
int cnt; // 每行合法状态个数
int s[M]; // 同一行的合法状态集个数
int num[M]; // 每个合法状态包含1的个数
int f[N][M][M]; // 110*1024*1024*4=440MB(int型4字节)
// f[i][a][b]:已放好前i行,第i行第a个状态,第i-1行第b个状态时能放置的最大数量

int main() {
	cin>>n>>m;
	// 预处理地图
	for(int i=1;i<=n;i++) {
		for(int j=0;j<m;j++) {
			char c;cin>>c;
			// 这个技巧很重要,如果是平原(即1)需要转换成二进制
			// m-j-1 是1需要偏移的长度,即出现在第几位,转换成二进制是多少
			if(c=='P') g[i]+=1<<(m-j-1); // 保存地图各行数值
		}
		printf("g[%d]=%d\n",i,g[i]);
	}
	// 预处理合法状态和1的个数
	// 枚举一行的所有状态
	for(int i=0;i<(1<<m);i++) {
		// 如果不存在11或101
		if(!(i&i>>1) && !(i&i>>2)) {
			s[cnt++]=i; // 保存这个合法状态
			// 统计这个合法状态包含1的个数,存进num
			for(int j=0;j<m;j++) {
				num[i]+=(i>>j&1); // j&1说明i偏移j位后末尾是1
			}
		}
	}
	// 打印所有合法状态看看
	cout<<"输出合法状态:>"<<endl;
	for(int i=0;i<cnt;i++) {
		printf("s[%d]=%d num[%d]=%d\n",i,s[i],i,num[i]);
	}
	// 状态计算
	// 1) 枚举行,多算两行,技巧同上
	// 直接输出f[n+2][0][0] 这样就不用枚举最后一行n的所有合法状态挑出最大值
	for(int i=1;i<=n+2;i++) {
		// 2) 枚举第i行合法状态
		for(int a=0;a<cnt;a++) {
			// 3) 枚举第i-1行合法状态
			for(int b=0;b<cnt;b++) {
				// 4) 枚举第i-2行合法状态
				for(int c=0;c<cnt;c++) {
					// 状态转移的条件
					if(!(s[a]&s[b]) && !(s[a]&s[c]) && !(s[b]&s[c]) // 任意两行不同列 
						&& (g[i]&s[a])==s[a] && (g[i-1]&s[b])==s[b]) // 地图适配a,地图适配b
					{
						// s[a]: 状态a的十进制表示,num[s[a]]: 取出本行状态为a时这一行的炮兵个数
						f[i][a][b]=max(f[i][a][b],f[i-1][b][c]+num[s[a]]);
						
						// 模拟跟踪状态转移过程
						printf("f[%d %d %d]=%d 由上一行 f[%d %d %d]=%d 加上本行炮兵个数 %d 转移而来\n",
							i,a,b,f[i][a][b],i-1,b,c,f[i-1][b][c],num[s[a]]);
					}
				}
			}
		}
	}
	cout<<f[n+2][0][0]<<endl; // 等价于枚举第n行a/b所有状态遍历得到的最大值 
	return 0;
}

/*
输入样例:
3 4
PHHP
HPHP
HHPH
输出样例:
4
 */

4.4. 延申-滚动数组优化

  • 在上述代码中 $f$ 数组是三维的，共占空间 $440MB$，如果题目限制为 $64MB$，那么肯定会 $MLE$，所以考虑如何压缩空间
  • 可以用滚动数组优化，因为状态转移时，第 $i$ 行只与第 $i-1$ 行有关，所以第一维可以只开 $2$ 个空间

4.4.1. 数据结构

1
2
3
4
5
6
7
8
const int N=110; // 最大行数
const int M=1<<10; // 列数最大为10,则状态最大有2^10-1
int n,m;
int g[N]; // 地图各行十进制表示数值
int cnt; // 每行合法状态个数
int s[M]; // 同一行的合法状态集个数
int num[M]; // 每个合法状态包含1的个数
int f[2][M][M]; // 2*1024*1024*4=8MB(int型4字节)

4.4.2. 状态计算部分修改

  • 因为第一维空间只有 $2$ 了，所以每次使用第一维空间时要模 $2$，也可以通过位运算的方式，使用 $&1$ 达到模 $2$ 的效果
  • 另外，对于 $i-1&1$ 的运算顺序是 $i-1$ 后再 $&1$ ，位运算的优先级通常较低
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 1) 计算的次数不变
for(int i=1;i<=n+2;i++) {
    // 2) 枚举第i行合法状态
    for(int a=0;a<cnt;a++) {
        // 3) 枚举第i-1行合法状态
        for(int b=0;b<cnt;b++) {
            // 4) 枚举第i-2行合法状态
            for(int c=0;c<cnt;c++) {
                // 状态转移的条件
                if(!(s[a]&s[b]) && !(s[a]&s[c]) && !(s[b]&s[c]) // 任意两行不同列 
                   && (g[i]&s[a])==s[a] && (g[i-1]&s[b])==s[b]) // 地图适配a,地图适配b
                {
                    // s[a]: 状态a的十进制表示,num[s[a]]: 取出本行状态为a时这一行的炮兵个数
                    f[i&1][a][b]=max(f[i&1][a][b],f[i-1&1][b][c]+num[s[a]]);

                    // 模拟跟踪状态转移过程
                    printf("f[%d %d %d]=%d 由上一行 f[%d %d %d]=%d 加上本行炮兵个数 %d 转移而来\n",
                           i&1,a,b,f[i&1][a][b],i-1&1,b,c,f[i-1&1][b][c],num[s[a]]);
                }
            }
        }
    }
}
cout<<f[n+2&1][0][0]<<endl; // 等价于枚举第n行a/b所有状态遍历得到的最大值

4.4.3. 完整代码

这里直接引用董晓老师的代码了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=110, M=1<<10;
int n,m;    //行数,列数 
int g[N];   //存储地图各行数值
int cnt;    //一行的合法状态个数
int s[M];   //一行的合法状态集 
int num[M]; //每个合法状态包含1的个数 
int f[2][M][M]; //滚动数组 2*1024*1024*4 = 8MB
// f[i][a][b]表示已放好前i行，
// 第i行第a个状态，第i-1行第b个状态时，能放置的最大数量 

int main(){
  cin>>n>>m;
  for(int i=1;i<=n;i++)
    for(int j=0;j<m;j++){
      char c; cin>>c; 
      if(c=='P') g[i]+=1<<(m-j-1); //地图各行数值          
    }
  
  for(int i=0; i<(1<<m); i++)   //枚举一行的所有状态 
    if(!(i&i>>1) && !(i&i>>2)){ //如果不存在11和101 
      s[cnt++]=i;               //保存一行的合法状态
      for(int j=0; j<m; j++)
      	num[i]+=(i>>j&1);         //每个合法状态包含1的个数
    }
  
  for(int i=1; i<=n+2; i++) //枚举行
  for(int a=0; a<cnt; a++)  //枚举第i行合法状态
  for(int b=0; b<cnt; b++)  //枚举第i-1行合法状态
  for(int c=0; c<cnt; c++)  //枚举第i-2行合法状态
    if(!(s[a]&s[b])&&!(s[a]&s[c])&&!(s[b]&s[c])
      &&(g[i]&s[a])==s[a]&&(g[i-1]&s[b])==s[b])
        f[i&1][a][b]=max(f[i&1][a][b],f[i-1&1][b][c]+num[s[a]]);
      
  cout<<f[n+2&1][0][0]<<endl;
  return 0;
}
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！

扫一扫，分享到微信

微信分享二维码
  • Copyrights © 2015-2024 John Doe
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信