正题

题目链接:https://www.luogu.com.cn/problem/P5074

---

题目大意

给出一个$n\times m$的网格，有的必须铺线有的不能，铺成若干条闭合回路，求方案数。

$1\le n,m\le 12$

---

解题思路

考虑插头$dp$，因为可以随意开回路，所以就没有严格匹配的限制了，可以直接用二进制记录每个位置有没有插头就好了。

时间复杂度：$O(nm{2}^m)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=13; ll T,n,m,v[N][N],f[2][1<<N]; signed main() {scanf("%lld",&T);while(T--){scanf("%lld%lld",&n,&m);for(ll x=0;x<n;x++)for(ll y=0;y<m;y++)scanf("%lld",&v[x][y]);ll o=0,MS=1<<m+1;f[o][0]=1;for(ll s=1;s<MS;s++)f[o][s]=0;for(ll x=0;x<n;x++){o^=1;for(ll s=0;s<MS;s++)f[o][s]=0;for(ll s=0;s<MS/2;s++)f[o][s<<1]=f[!o][s];for(ll y=0;y<m;y++){o^=1;for(ll s=0;s<MS;s++)f[o][s]=0;for(ll s=0;s<MS;s++){ll u=(s>>y+1)&1,l=(s>>y)&1,g=f[!o][s];if(!g)continue;if(!v[x][y]){if(!u&&!l)f[o][s]+=g;}else{if(!u&&!l)f[o][s|(1<<y)|(1<<y+1)]+=g;else if(u&&!l){f[o][s]+=g;//转右 f[o][s^(1<<y)^(1<<y+1)]+=g;//转下 }else if(!u&&l){f[o][s]+=g;//转下 f[o][s^(1<<y)^(1<<y+1)]+=g;//转右}else{f[o][s^(1<<y)^(1<<y+1)]+=g;}}}}}printf("%lld\n",f[o][0]);}return 0; } 创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的P5074-Eat the Trees【插头dp】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。