洛谷P1879-玉米田(状压dp)

题意：洛谷P1879

这道题目可以说是炮兵阵地和互不侵犯的合成简化版，给定一个$N\ast M$的图，$1$表示可以种玉米，$0$表示不可以种玉米，若选择$1$个格子种下玉米，那么这个格子的上下左右格子不能再种玉米，问有多少种种玉米的方案。

分析：

先将读入的图转为二进制数，此时的二进制数中$1$表示不能种玉米，$0$表示能种玉米。然后预处理一行内所有可行的种玉米状态，再预处理第一行所有可行状态的方案数(即为1)。从第二行开始向下状态转移即可，最终答案就是最后一行的所有状态的方案数之和。状态转移方程： $dp[i][j]+=dp[i-1][k]$，$i$表示当前行，$j$表示当前行状态，$k$表示上一行状态。 值得注意的是状态转移的时候要判断$j、k$的状态合法性。

$AC$代码$1$：

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 500 + 5; const ll mod = 100000000; int n, m, x, cnt, maxsta, sta[maxn], num[maxn], pic[15]; ll ans, dp[15][maxn]; int main(){ scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ scanf("%d", &x); if(x == 0) pic[i] += (1 << (j - 1)); } } maxsta = 1 << m; for(int i = 0; i < maxsta; i++) if(!(i & (i << 1)) && !(i & (i >> 1))){ sta[++cnt] = i; } for(int i = 1; i <= cnt; i++) if(!(sta[i] & pic[1])){ dp[1][i] = 1; } for(int i = 2; i <= n; i++){ for(int j = 1; j <= cnt; j++){ if(sta[j] & pic[i]) continue;//当前行状态不能和当前行的图有冲突 for(int k = 1; k <= cnt; k++){ if(sta[k] & pic[i - 1] || sta[k] & sta[j]) continue;//上一行状态不能和上一行图有冲突，也不能和当前行状态有冲突 dp[i][j] = (dp[i][j] % mod + dp[i - 1][k] % mod) % mod; } } } for(int i = 1; i <= cnt; i++) ans = (ans % mod + dp[n][i] % mod) % mod; printf("%lld\n", ans); return 0; }

刚开始瞎写的三维状压$dp$也过了。 $AC$代码$2$：

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 500 + 5; const ll mod = 100000000; int n, m, x, cnt, maxsta, sta[maxn], num[maxn], pic[15]; ll ans, dp[15][maxn][maxn]; int main(){ scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ scanf("%d", &x); if(x == 0) pic[i] += (1 << (j - 1)); } } maxsta = 1 << m; for(int i = 0; i < maxsta; i++) if(!(i & (i << 1)) && !(i & (i >> 1))){ sta[++cnt] = i; } for(int i = 1; i <= cnt; i++) if(!(sta[i] & pic[1])){ dp[1][i][1] = 1; } for(int i = 2; i <= n; i++){ for(int j = 1; j <= cnt; j++){ if(sta[j] & pic[i]) continue; for(int k = 1; k <= cnt; k++){ if(sta[k] & pic[i - 1] || sta[j] & sta[k]) continue; for(int l = 1; l <= cnt; l++){ if(sta[l] & pic[i - 2] || sta[l] & sta[k]) continue; dp[i][j][k] = (dp[i][j][k] % mod + dp[i - 1][k][l] % mod) % mod; } } } } for(int i = 1; i <= cnt; i++){ for(int j = 1; j <= cnt; j++){ ans = (ans % mod + dp[n][i][j] % mod) % mod; } } printf("%lld\n", ans); return 0; }