正題

題目鏈接:https://www.luogu.com.cn/problem/P5056

---

題目大意

$n?m$的網(wǎng)格，求有多少條回路可以鋪滿整個(gè)棋盤。

---

解題思路

插頭$dp$的，寫法是按照題解上的寫法。

狀態(tài)用的是括號(hào)匹配，然后用了哈希+鄰接表（掛表）還有滾動(dòng)數(shù)組優(yōu)化空間

然后可以看題解學(xué)

---

code

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int P=133331; struct node{int to,next; }a[P*2]; int n,m,o,tot,zx,zy,t[2],bit[25],ls[P],S[2][P],v[25][25]; long long ans,dp[2][P]; char st[25]; void Add(int s,long long v){int x=s%P;for(int i=ls[x];i;i=a[i].next)if(S[o][a[i].to]==s){dp[o][a[i].to]+=v;return;}t[o]++;dp[o][t[o]]=v;S[o][t[o]]=s;a[++tot].to=t[o];a[tot].next=ls[x];ls[x]=tot;return; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",st+1);for(int j=1;j<=m;j++)if(st[j]=='.'){v[i][j]=1;zx=i;zy=j;}}for(int i=0;i<=12;i++)bit[i]=(1<<(i<<1));t[o]=1;S[o][1]=0;dp[o][1]=1;for(int i=1;i<=n;i++){for(int j=1;j<=t[o];j++)S[o][j]<<=2;//將右插頭移到最左邊 for(int j=1;j<=m;j++){o^=1;tot=t[o]=0;memset(ls,0,sizeof(ls));int s,dpl,rpl;long long w;for(int k=1;k<=t[!o];k++){s=S[!o][k];w=dp[!o][k];dpl=(s>>(j<<1))%4;rpl=(s>>(j-1<<1))%4;if(!v[i][j]){//障礙 if(!dpl && !rpl)Add(s,w);//不能有插頭 }else if(!dpl && !rpl){//兩邊都沒有插頭if(v[i+1][j]&&v[i][j+1])//開一個(gè)左上角插頭 Add(s+2*bit[j]+bit[j-1],w);} else if(!dpl && rpl){//只有右插頭 if(v[i+1][j])Add(s,w);if(v[i][j+1])Add(s-rpl*bit[j-1]+rpl*bit[j],w);}else if(dpl && !rpl){//只有下插頭if(v[i+1][j])Add(s-dpl*bit[j]+dpl*bit[j-1],w);if(v[i][j+1])Add(s,w); }else if(dpl==1&&rpl==1){int c=1;for(int p=j+1;p<=m;p++){if((s>>(p<<1))%4==1)c++;if((s>>(p<<1))%4==2)c--;if(!c){Add(s-bit[j]-bit[j-1]-bit[p],w);break;}}}else if(dpl==2&&rpl==2){int c=1;for(int p=j-2;p>=0;p--){if((s>>(p<<1))%4==2)c++;if((s>>(p<<1))%4==1)c--;if(!c){Add(s-2*bit[j]-2*bit[j-1]+bit[p],w);break;}}}else if(dpl==1&&rpl==2)Add(s-2*bit[j-1]-bit[j],w);else if(dpl==2&&rpl==1)if(i==zx&&j==zy)ans+=w;}}}printf("%lld\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P5056-[模板]插头dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。