【YBT2022寒假Day1 B】方格填写(插头DP)
2022/2/6 6:13:52
本文主要是介绍【YBT2022寒假Day1 B】方格填写(插头DP),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
方格填写
题目链接:YBT2022寒假Day1 B
题目大意
有一个二维网格,然后里面每个位置要放一个 0~4 的数有一些已经填好的,也有要你填的。
然后一个位置可以跟相邻的四个点连边,然后要求一个点的边数量等于填的数字。
然后问你所有填写方案边的匹配方案数的平方的和。
思路
考虑这个平方的意义。
它其实是可以变成你选任意一种填数方式,在这中间任选两个匹配方案的方案数。
那我们就可以状压,因为看到状态很小,我们可以这样插头 DP:
\(f_{i,j,k,l}\) 为当前搞到 \((i,j)\) 的位置,两个方案的状态分别是 \(k,l\)。(\(k,l\) 是 \(m+1\) 位的状压,维护 \(m\) 个向下的,一个向右的)
然后转移一下即可,要注意的是要滚动数组。
代码
#include<cstdio> #include<cstring> #define ll long long #define mo 998244353 using namespace std; int T, n, m, a[71][7], aa[5], bb[5]; ll f[2][128][128]; int main() { freopen("grid.in", "r", stdin); freopen("grid.out", "w", stdout); scanf("%d", &T); while (T--) { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]); memset(f, 0, sizeof(f)); f[0][0][0] = 1; int now = 1; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) { if (a[i][j] != -1) { for (int fr = 0; fr < (1 << (m + 1)); fr++) { for (int frr = 0; frr < (1 << (m + 1)); frr++) { int to = fr, too = frr; int num = a[i][j], numm = a[i][j]; if (j == 1 && ((to >> m) & 1)) continue; if (j == 1 && ((too >> m) & 1)) continue; if ((to >> m) & 1) num--, to -= (1 << m); if ((to >> (j - 1)) & 1) num--, to -= (1 << (j - 1)); if ((too >> m) & 1) numm--, too -= (1 << m); if ((too >> (j - 1)) & 1) numm--, too -= (1 << (j - 1)); if (num < 0 || numm < 0 || num > 2 || numm > 2) continue; if (!f[now ^ 1][fr][frr]) continue; ll x = f[now ^ 1][fr][frr]; if (num == 0) aa[0] = 1, aa[1] = 0; else if (num == 1) aa[0] = 2, aa[1] = (1 << m), aa[2] = (1 << (j - 1)); else if (num == 2) aa[0] = 1, aa[1] = (1 << m) | (1 << (j - 1)); if (numm == 0) bb[0] = 1, bb[1] = 0; else if (numm == 1) bb[0] = 2, bb[1] = (1 << m), bb[2] = (1 << (j - 1)); else if (numm == 2) bb[0] = 1, bb[1] = (1 << m) | (1 << (j - 1)); for (int ii = 1; ii <= aa[0]; ii++) for (int jj = 1; jj <= bb[0]; jj++) (f[now][to | aa[ii]][too | bb[jj]] += x) %= mo; } } } else { for (int qq = 0; qq <= 4; qq++) { for (int fr = 0; fr < (1 << (m + 1)); fr++) { for (int frr = 0; frr < (1 << (m + 1)); frr++) { int to = fr, too = frr; int num = qq, numm = qq; if (j == 1 && ((to >> m) & 1)) continue; if (j == 1 && ((too >> m) & 1)) continue; if ((to >> m) & 1) num--, to -= (1 << m); if ((to >> (j - 1)) & 1) num--, to -= (1 << (j - 1)); if ((too >> m) & 1) numm--, too -= (1 << m); if ((too >> (j - 1)) & 1) numm--, too -= (1 << (j - 1)); if (num < 0 || numm < 0 || num > 2 || numm > 2) continue; if (!f[now ^ 1][fr][frr]) continue; ll x = f[now ^ 1][fr][frr]; if (num == 0) aa[0] = 1, aa[1] = 0; else if (num == 1) aa[0] = 2, aa[1] = (1 << m), aa[2] = (1 << (j - 1)); else if (num == 2) aa[0] = 1, aa[1] = (1 << m) | (1 << (j - 1)); if (numm == 0) bb[0] = 1, bb[1] = 0; else if (numm == 1) bb[0] = 2, bb[1] = (1 << m), bb[2] = (1 << (j - 1)); else if (numm == 2) bb[0] = 1, bb[1] = (1 << m) | (1 << (j - 1)); for (int ii = 1; ii <= aa[0]; ii++) for (int jj = 1; jj <= bb[0]; jj++) (f[now][to | aa[ii]][too | bb[jj]] += x) %= mo; } } } } now ^= 1; memset(f[now], 0, sizeof(f[now])); } printf("%lld\n", f[now ^ 1][0][0]); } return 0; }
这篇关于【YBT2022寒假Day1 B】方格填写(插头DP)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?