状态 表示 前 i 行状态为 mask的 合法方案数量
状态转移方程为
其中 状态 j,k 满足条件 j & k = 0, j & ( j <<1) = 0, k & ( k <<1 ) = 0 ,且 J,K状态种植点合法
因为两层间种植的点, 不可以上下相邻 所以有 J&K = 0
因为同层间,种植点不可 两两相邻, 所以有 J & ( J << 1 ) = 0 , K & ( K << 1 ) = 0
再而, 对于当前层, 某些点不可以 种植, 某些可以种植, 因为只有12位, 我们可以映射到一个 int 值使用位表示.
定义状态 mask( i ) 表示 第 I 层的 M个位置 种植状态情况, 若 可种植为值为0, 不可种植为 1
则 对于任意 行 状态 按位与上 该行种植情况: mask ( i ) & J = 0 则 表示当前合法, 无非法种植点
解题代码
View Code
#include<stdio.h> #include<stdlib.h> #include<string.h> typedef long long LL; const int mod = 1e8; LL dp[15][(1<<12)+10]; int mp[15][15], d[15]; int n, m, Max; bool legal( int k, int mask ) { if( (mask & d[k]) > 0 ) return false; return true; } void print(int k) { for(int j = 0; j < Max; j++) printf("%4lld", dp[k][j]); puts(""); } int main() { while( scanf("%d%d", &n,&m) != EOF) { memset( d,0,sizeof(d)); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) { scanf("%d",&mp[i][j]); d[i] += ( mp[i][j] ? 0 : (1<<j) ); } memset( dp, 0, sizeof(dp) ); Max = (1<<m); for(int mask = 0; mask < Max; mask++) if( legal( 0, mask ) && ((mask &(mask<<1)) == 0) ) dp[0][mask] = 1; // print(0); for(int i = 1; i < n; i++) { for(int j = 0; j < Max; j++) { for(int mask = 0; mask < Max; mask++) { if( legal(i,j) && legal(i-1,mask) ) { if( ((j&mask)==0 ) && ((j&(j<<1))== 0) && ((mask&(mask<<1)) == 0) ) dp[i][j] = (dp[i][j]+dp[i-1][mask])%mod; } } } // print(i); } LL ans = 0; for(int mask = 0; mask < Max; mask++) { if( legal(n-1,mask ) && ((mask&(mask<<1)) == 0 ) ) ans = (ans+dp[n-1][mask])%mod; } printf("%lld\n", ans ); } return 0; }