题目链接:
洛谷题目入口
/YbtOJ-高效进阶-状压dp-A.【例题1】 种植方案
解析在代码里:
#include <bits/stdc++.h>
using namespace std;
const int Mod = 1e8;
int m, n, f[13][4097], F[13];
bool field[13][13];
bool state[4097];
// max state: (111111111111)2 =(2^12)10 = (4096)10
int main()
{
scanf("%d%d",&m,&n);
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
scanf("%d",&field[i][j]);
//
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
F[i] = (F[i] << 1) + field[i][j];
// F[i]:保存第i行的艹地肥沃情况为二进制数,方便后续处理
int MAX_STATE = 1 << n;
//二进制中有n位,对于十进制表现为有2^n大的总方案数
for (int i = 0; i < MAX_STATE; i++)
state[i] = ((i&(i<<1))==0) && ((i&(i>>1))==0);
// 记录所有可分配方案:枚举所有小于总方案数的十进制数字,
// 判断其转化为二进制后显示的方案是否可行,行则state[i]为ture
//
// 具体地:使该方案整体左移,若&的结果为零,则没有任何
// 选择的土地向左的临近被选择。向右同理。
//
// *举例:当该块土地被选择时,对应的该二进制数的该位为1,则
// 10101显然为一个合理方案: // 11001显然为一个不合理方案:
// 010101 // 011001
// & 101010(此处为左移情况) // & 110010(此处为左移情况)
// = 000000 // = 010000
f[0][0] = 1;
for (int i = 1; i <= m; i++){
//枚举每行
for (int j = 0; j < MAX_STATE; j++){
//枚举所有可能方案
if (state[j] && ((j & F[i]) == j)){
//state[j]判定该方案j可行
//&&之后的部分判定方案j所选的草地是否足够肥沃
//
//*举例:已知,经过前面state的确认,
//此时j表示的是一个可行的二进制方案,则
//如有j=21(10)=10101(2),F[i]=29(10)=11101(2)
// 10101 = j
//& 11101 = F[i]
//= 10101 = j
//借助按位与(&)的性质,我们发现:
//当j为1的数位与F[i]同为1时,二者&的结果为j。
//
//至此,我们完成了对该方案j可行性的判定。
for (int k = 0; k < MAX_STATE; k++){
//再枚举每种可能方案从上一行进行状态转移
if ((k & j) == 0){
//这里意思是:k与j每一位都不同
//因为上下也算是相邻
//保证继承的上一行的方案数是与自己匹配的
//不然不不就不符题意了嘛
//还搞不懂就这回自己举例
f[i][j] = (f[i][j] + f[i-1][k]) % Mod;
//继承上一行的可能方案为k的方案数
//如果上一行的该方案不符合要求,那么加了也没值
//第一行只能从f[0][0]得到第一行属于自己的那份方案数
//此后每一行得以继承上一行所有与自己匹配的方案的值(if中的条件)
}
}
}
}
}
int ans = 0;
for (int i = 0; i < MAX_STATE; i++)
ans = (ans + f[m][i]) % Mod;
//方案数由上一行继承过来
//那么最终答案就都在最后一行啦
//把最后一行统计至此的方案数全部加起来就好啦!
printf("%d\n",ans);
return 0;
}