状压 dp 还不熟啊...
这是状压 dp 例题后面的基础练习题了. 可以看 "互不侵犯" 这道题.
状态表示方法类似, 只不过没有第三维即数量的限制: 设 \(dp[i][j]\) 为前 \(i\) 行, 第 \(i\) 行状态为 \(j\) 时的方案数.
状态转移方程简直不能再简单:\(dp[i][k] = sum(dp[i - 1][j])\), 其中 \(j\) 是上一行的状态.
首先当然预处理, 减小重复的筛除不合法时间.
这道题的限制条件是任意两片田不能相邻, 即上下左右不能有田.
左右的容易解决, 拿自己和自己左移一位 \(and\) 一下即可.
上下的在递推的时候更容易解决, 直接 \(and\).
注意: 二进制运算的优先级很低, 非常低, 所以有二进制的时候一定要打好括号!!!
代码:
- #include<cstdio>
- const int maxn = 14;
- const int mod = 100000000;
- int n, m;
- long long dp[maxn][1 << maxn];
- int status[1 << maxn], tot;
- int check[maxn];
- long long ans;
- int maxl;
- void init()
- {
- }
- int main()
- {
- scanf("%d%d", &n, &m);
- for(int i = 1; i <= n; i++)
- {
- for(int j = 1; j <= m; j++)
- {
- int temp; scanf("%d", &temp);
- check[i] = check[i] << 1 | temp;
- }
- }
- maxl = 1 << m;
- for(int i = 0; i < maxl; i++)
- {
- if(!(i & (i << 1)))
- {
- status[++tot] = i;
- if((i & check[1]) == i)
- {
- dp[1][i] = 1;
- }
- }
- }
- //for(int i = 1; i <= tot; i++) printf("%d\n", dp[1][status[i]]);
- for(int i = 2; i <= n; i++)
- {
- for(int j = 1; j <= tot; j++)
- {
- for(int k = 1; k <= tot; k++)
- {
- if((status[j] & check[i - 1]) != status[j]) continue;
- if((status[k] & check[i]) != status[k]) continue;
- if(status[j] & status[k]) continue;
- dp[i][status[k]] = (dp[i][status[k]] + dp[i - 1][status[j]]) % mod;
- }
- }
- }
- for(int i = 1; i <= tot; i++) ans = (ans + dp[n][status[i]]) % mod;
- printf("%lld\n", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2741072.html