#|ACWING327. 玉米田（状压dp） #|状压dp|算法竞赛进阶指南

农夫约翰的土地由M*N个小方格组成，现在他要在土地里种植玉米。
非常遗憾，部分土地是不育的，无法种植。
而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。
现在给定土地的大小，请你求出共有多少种种植方法。
土地上什么都不种也算一种方法。
输入格式
第1行包含两个整数M和N。
第2…M+1行：每行包含N个整数0或1，用来描述整个土地的状况，1表示该块土地肥沃，0表示该块土地不育。
输出格式
输出总种植方法对100000000取模后的值。
数据范围
1≤M,N≤12
输入样例：
2 3
1 1 1
0 1 0
输出样例：
9
思路：基础状压，f(i,j)表示到了第i行状态为j有多少种放置方式。
【#|ACWING327. 玉米田（状压dp）】ACNEW ：把状态预处理一遍

#include #include #include using namespace std; typedef long long ll; const int mod = 1e9; ll sta[1 << 13],a[13]; ll f[13][1 << 13]; ll right[1 << 13]; bool judge1(ll s) { if(s & (s << 1))return false; return true; }bool judge2(ll s1,ll s2) { if(s1 & s2)return false; return true; }bool judge3(ll s1,ll s2) { if((s1 | s2) != s1)return false; return true; }int main() { ll n,m; scanf("%lld%lld",&n,&m); for(ll i = 1; i <= n; i++) { for(ll j = 0; j < m; j++) { ll tmp; scanf("%lld",&tmp); if(tmp) { a[i] = a[i] | (1 << j); } } }ll cnt = 0; for(ll i = 0; i < (1 << m); i++) { if(judge1(i) && judge3(a[1],i))f[1][i] = 1; if(judge1(i))right[++cnt] = i; }for(ll i = 2; i <= n; i++) { for(ll now = 1; now <= cnt; now++) { if(judge3(a[i],right[now])) { for(ll pre = 1; pre <= cnt; pre++) { if(judge2(right[now],right[pre])) { f[i][right[now]] += f[i - 1][right[pre]]; } } } } }ll ans = 0; for(ll i = 0; i < (1 << m); i++) { ans = (ans + f[n][i]) % mod; }printf("%lld\n",ans); return 0; }

#include #include #include #include using namespace std; const int MOD = 100000000; int f[13][1 << 12],a[13][13],sta[13]; bool ok2(int s1,int s2) { if((s1 & s2) == 0) return true; return false; }bool ok3(int s) { if((s & (s >> 1)) == 0) return true; return false; }int main() { int n,m; scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { scanf("%d",&a[i][j]); if(a[i][j] == 1) sta[i] |= (1 << (j - 1)); } }for(int i = 0; i < (1 << m); i++) { if(((i & sta[1]) == i) && ok3(i)) f[1][i] = 1; }for(int i = 2; i <= n; i++) { for(int j = 0; j < (1 << m); j++) { if(ok3(j) && ((j & sta[i]) == j)) { for(int k = 0; k < (1 << m); k++) { if(!(j & k)) { f[i][j] = (f[i - 1][k] + f[i][j]) % MOD; ; } } } } }int ans = 0; for(int j = 0; j < (1 << m); j++) ans = (ans + f[n][j]) % MOD; printf("%d\n",ans); return 0; }