P5056 【模板】插头dp

雨点打透心脏的1/2处 2021-12-23 14:05 82阅读 0赞

### 思路 ###

插头DP的模板  
插头DP括号序列的方法其实就是利用回路不能交叉匹配，必定两两配对的性质通过括号序列描述了连通块的匹配关系  
注意分类讨论、判断状态合法  
**最边上一圈不能有插头延伸过去，要注意**

### 代码 ###

#include <cstdio> #include <algorithm> #include <cstring> #define int long long using namespace std; int val[2][100001],times[2][100001],now,fir[100001],nxt[100001],cnt[2],n,m,endx,endy,mat[20][20],ans=0,last,pos[40]; const int MOD = 100001; void insert(int c,int num){ int t=c%MOD,i; for(i=fir[t];i;i=nxt[i]){ if(val[now][i]==c){ times[now][i]+=num; return; } } ++cnt[now]; val[now][cnt[now]]=c; times[now][cnt[now]]=num; nxt[cnt[now]]=fir[t]; fir[t]=cnt[now]; } int Getchar(void){ char c=getchar(); while(c!='*'&&c!='.') c=getchar(); if(c=='*') return 1; else return 0; } int getval(int x,int pos){ return (x>>((pos-1)*2))%4; } // void print(int x){ // for(int i=0;i<2*(m+1);i++){ // printf("%lld",(x>>i)&1); // } // printf("\n"); // } void dp(void){ now=0; insert(0,1); for(int i=1;i<=n;i++){ for(int j=1;j<=cnt[now];j++) val[now][j]<<=2; for(int j=1;j<=m;j++){ last=now; now^=1; cnt[now]=0; // printf("i=%lld j=%lld\n",i,j); // for(int k=1;k<=cnt[last];k++) // print(val[last][k]); memset(fir,0,sizeof(fir)); memset(nxt,0,sizeof(nxt)); for(int k=1;k<=cnt[last];k++){ int state=val[last][k],num=times[last][k],plugL=getval(state,j),plugU=getval(state,j+1); //新建一个联通分量 if(!mat[i][j]){ if((!plugL)&&(!plugU)){ if((!mat[i][j+1])&&(!mat[i+1][j])) insert(state+pos[(j-1)*2]+pos[j*2+1],num); } //合并两个联通分量 else if(plugL&&plugU){ if(plugL==1&&plugU==2){ if(i==endx&&j==endy){ // printf("i=%lld j=%lld num=%lld\n",i,j,num); // print(state); ans+=num; } } if(plugL==2&&plugU==1){ insert(state-pos[(j-1)*2+1]-pos[j*2],num); } if(plugL==1&&plugU==1){ int k1=1; for(int l=j+2;l<=m+1;l++){ if(getval(state,l)==0) continue; if(getval(state,l)==1) k1++; if(getval(state,l)==2) k1--; if(!k1){ insert(state-pos[(j-1)*2]-pos[j*2]-pos[(l-1)*2],num); break; } } } if(plugL==2&&plugU==2){ int k2=1; for(int l=j-1;l>=1;l--){ if(getval(state,l)==0) continue; if(getval(state,l)==1) k2--; if(getval(state,l)==2) k2++; if(!k2){ insert(state-pos[(j-1)*2+1]-pos[j*2+1]+pos[(l-1)*2],num); break; } } } } //延续一个联通分量 else{ if(plugL&&(!plugU)){ //左->下 if(!mat[i+1][j]) insert(state,num); //左->左 if((!mat[i][j+1])) insert(state-pos[(j-1)*2]*plugL+pos[j*2]*plugL,num); } if(plugU&&(!plugL)){ //上->上 if(!mat[i+1][j]){ insert(state-pos[j*2]*plugU+pos[(j-1)*2]*plugU,num); } //上->左 if(!mat[i][j+1]) insert(state,num); } } } else{ if((!plugL)&&(!plugU)){ insert(state,num); } } } } } } signed main(){ // freopen("test.out","w",stdout); scanf("%lld %lld",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ mat[i][j]=Getchar(); if(mat[i][j]==0){ endx=i; endy=j; } } for(int i=0;i<=m+1;i++) mat[0][i]=mat[n+1][i]=1; for(int i=1;i<=n;i++) mat[i][0]=mat[i][m+1]=1; // for(int i=1;i<=n;i++){ // for(int j=1;j<=m;j++) // printf("%lld ",mat[i][j]); // printf("\n"); // } pos[0]=1; for(int i=1;i<30;i++) pos[i]=pos[i-1]<<1; // for(int i=0;i<30;i++) // printf("%lld\n",pos[i]); dp(); printf("%lld",ans); return 0; }

转载于:https://www.cnblogs.com/dreagonm/p/10836949.html