正題

題目鏈接: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】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。