登录
← 返回首页 | 代码片段 › 5 动态规划 › 5.4 插头DP › 插头DP / 搜索
JSON MD

5.4 插头DP

插头DP Eat the Trees
46 行
CPP JSON
【插头DP(Eat the Trees)】 插头 DP(Plug DP / 轮廓线 DP)模板,用于网格路径覆盖问题。 核心函数: void in(Re &x) — 核心算法函数 关键配置: N=15,M=8192+3 复杂度:时间复杂度取决于状态数和转移复杂度 说明:freopen("123.txt","r",stdin); 适用场景:网格上的路径覆盖/回路计数问题(如哈密顿回路、多米诺覆盖)
C++ 45 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=15,M=8192+3;
int n,m,o,V,T,A[N][N];LL dp[2][M];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(T);
	while(T--){
		in(n),in(m),V=(1<<m+1)-1;
		for(Re i=1;i<=n;++i)
			for(Re j=1;j<=m;++j)
				in(A[i][j]);
		for(Re j=0;j<=V;++j)dp[0][j]=dp[1][j]=0;
		dp[o][0]=1;
		for(Re i=1;i<=n;++i){
			o^=1;
			for(Re s=0;s<=V;++s)dp[o][s]=(s&1)?0:dp[o^1][s>>1];
			for(Re j=1;j<=m;++j){
				o^=1;
				for(Re s=0;s<=V;++s)dp[o][s]=0;
				for(Re s=0;s<=V;++s)if(dp[o^1][s]){
					Re L=(s>>j-1)&1,U=(s>>j+1-1)&1;
					if(A[i][j]){// 撤销操作
						dp[o][s^(1<<j-1)^(1<<j+1-1)]+=dp[o^1][s];
						if(L!=U)dp[o][s]+=dp[o^1][s];
					}
					else{
						if(!L&&!U)dp[o][s]+=dp[o^1][s];
					}
				}
			}
		}
		printf("%lld\n",dp[o][0]);
	}
}
插头DP (括号表示法) 单回路
60 行
CPP JSON
【插头DP (括号表示法)(单回路)】 插头 DP(Plug DP / 轮廓线 DP)模板,用于网格路径覆盖问题。 核心函数: void in(Re &x) — 核心算法函数 关键配置: N=14,M=1594323+3 复杂度:时间复杂度取决于状态数和转移复杂度 说明:freopen("123.txt","r",stdin);;printf("edx=%d, edy=%d\n",edx,edy); 适用场景:网格上的路径覆盖/回路计数问题(如哈密顿回路、多米诺覆盖)
C++ 59 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=14,M=1594323+3;
int n,m,o,V,edx,edy,Mi[N],A[N][N];LL ans,dp[2][M];char s[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),Mi[0]=1;
	for(Re i=1;i<=m+1;++i)Mi[i]=Mi[i-1]*3;V=Mi[m+1]-1;
	for(Re i=1;i<=n;++i){
		scanf("%s",s+1);
		for(Re j=1;j<=m;++j)if(!(A[i][j]=(s[j]=='*')))edx=i,edy=j;
	}
//	printf("edx=%d, edy=%d\n",edx,edy);
	dp[o][0]=1;
	for(Re i=1;i<=n;++i){
		o^=1;
		for(Re s=0;s<=V;++s)dp[o][s]=s%3?0:dp[o^1][s/3];
		for(Re j=1;j<=m;++j){
			o^=1;
			for(Re s=0;s<=V;++s)dp[o][s]=0;
			for(Re s=0;s<=V;++s)if(dp[o^1][s]){
				Re L=s/Mi[j-1]%3,U=s/Mi[j+1-1]%3;
				if(A[i][j]){if(!L&&!U)dp[o][s]+=dp[o^1][s];}
				else if(!L&&!U)dp[o][s+Mi[j-1]+2*Mi[j+1-1]]+=dp[o^1][s];
				else if(!L&&U)dp[o][s]+=dp[o^1][s],dp[o][s+U*Mi[j-1]-U*Mi[j+1-1]]+=dp[o^1][s];
				else if(L&&!U)dp[o][s]+=dp[o^1][s],dp[o][s-L*Mi[j-1]+L*Mi[j+1-1]]+=dp[o^1][s];
				else if(L==1&&U==1){
					Re cnt=1;
					for(Re k=j+2;k<=m;++k){
						if(s/Mi[k-1]%3==1)++cnt;
						else if(s/Mi[k-1]%3==2)--cnt;
						if(!cnt){dp[o][s-Mi[j-1]-Mi[j+1-1]-Mi[k-1]]+=dp[o^1][s];break;}
					}
				}
				else if(L==2&&U==2){
					Re cnt=1;
					for(Re k=j-1;k>=1;--k){
						if(s/Mi[k-1]%3==1)--cnt;
						else if(s/Mi[k-1]%3==2)++cnt;
						if(!cnt){dp[o][s-2*Mi[j-1]-2*Mi[j+1-1]+Mi[k-1]]+=dp[o^1][s];break;}
					}
				}
				else if(L==2&&U==1)dp[o][s-2*Mi[j-1]-Mi[j+1-1]]+=dp[o^1][s];
				else if(L==1&&U==2)if(i==edx&&j==edy&&!(s-Mi[j-1]-2*Mi[j+1-1]))ans+=dp[o^1][s];
			}
		}
	}
	printf("%lld\n",ans);
}
插头DP (括号表示法+优化状态枚举) 单回路
70 行
CPP JSON
【插头DP (括号表示法+优化状态枚举)(单回路)】 插头 DP(Plug DP / 轮廓线 DP)模板,用于网格路径覆盖问题。 核心函数: void in(Re &x) — 核心算法函数 void add(Re s,LL v) — 加法更新 void CL(无参数) — 核心算法函数 关键配置: N=14,M=1594323+3 复杂度:时间复杂度取决于状态数和转移复杂度 说明:freopen("123.txt","r",stdin);;printf("edx=%d, edy=%d\n",edx,edy); 适用场景:网格上的路径覆盖/回路计数问题(如哈密顿回路、多米诺覆盖)
C++ 69 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=14,M=1594323+3;
int n,m,o,V,edx,edy,Mi[N],A[N][N];LL ans,dp[2][M];char s[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int st[2][M];
inline void add(Re s,LL v){
	if(!dp[o][s])st[o][++st[o][0]]=s;
	dp[o][s]+=v;
}
inline void CL(){
	for(Re i=1;i<=st[o][0];++i)dp[o][st[o][i]]=0;
	st[o][0]=0;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m),Mi[0]=1;
	for(Re i=1;i<=m+1;++i)Mi[i]=Mi[i-1]*3;V=Mi[m+1]-1;
	for(Re i=1;i<=n;++i){
		scanf("%s",s+1);
		for(Re j=1;j<=m;++j)if(!(A[i][j]=(s[j]=='*')))edx=i,edy=j;
	}
//	printf("edx=%d, edy=%d\n",edx,edy);
	dp[o][st[o][++st[o][0]]=0]=1;
	for(Re i=1;i<=n;++i){
		o^=1,CL();
		for(Re I=1;I<=st[o^1][0];++I)if(st[o^1][I]*3<=V&&dp[o^1][st[o^1][I]])
			dp[o][st[o][++st[o][0]]=st[o^1][I]*3]=dp[o^1][st[o^1][I]];
		for(Re j=1;j<=m;++j){
			o^=1,CL();
			for(Re I=1;I<=st[o^1][0];++I)if(dp[o^1][st[o^1][I]]){
				Re s=st[o^1][I];LL v=dp[o^1][s];
				Re L=s/Mi[j-1]%3,U=s/Mi[j+1-1]%3;
				if(A[i][j]){if(!L&&!U)add(s,v);}
				else if(!L&&!U)add(s+Mi[j-1]+2*Mi[j+1-1],v);
				else if(!L&&U)add(s,v),add(s+U*Mi[j-1]-U*Mi[j+1-1],v);
				else if(L&&!U)add(s,v),add(s-L*Mi[j-1]+L*Mi[j+1-1],v);
				else if(L==1&&U==1){
					Re cnt=1;
					for(Re k=j+2;k<=m;++k){
						if(s/Mi[k-1]%3==1)++cnt;
						else if(s/Mi[k-1]%3==2)--cnt;
						if(!cnt){add(s-Mi[j-1]-Mi[j+1-1]-Mi[k-1],v);break;}
					}
				}
				else if(L==2&&U==2){
					Re cnt=1;
					for(Re k=j-1;k>=1;--k){
						if(s/Mi[k-1]%3==1)--cnt;
						else if(s/Mi[k-1]%3==2)++cnt;
						if(!cnt){add(s-2*Mi[j-1]-2*Mi[j+1-1]+Mi[k-1],v);break;}
					}
				}
				else if(L==2&&U==1)add(s-2*Mi[j-1]-Mi[j+1-1],v);
				else if(L==1&&U==2)if(i==edx&&j==edy&&!(s-Mi[j-1]-2*Mi[j+1-1]))ans+=v;
			}
		}
	}
	printf("%lld\n",ans);
}
地板 三进制插头dp
77 行
CPP JSON
【地板(三进制插头dp)】 插头 DP(Plug DP / 轮廓线 DP)模板,用于网格路径覆盖问题。 核心函数: void in(Re &x) — 核心算法函数 void mo(Re &x) — 核心算法函数 关键配置: N=103,M=177147+3,P=20110520 复杂度:时间复杂度取决于状态数和转移复杂度 说明:freopen("123.txt","r",stdin); 适用场景:网格上的路径覆盖/回路计数问题(如哈密顿回路、多米诺覆盖)
C++ 76 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=103,M=177147+3,P=20110520;
int n,m,o,V,Mi[N],A[N][N],A_[N][N],dp[2][M];char s[N];//0:没有插头 1:还没完成的插头 2:已经完成的插头
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline void mo(Re &x){if(x>P)x-=P;}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	for(Re i=1;i<=n;++i){
		scanf("%s",s+1);
		for(Re j=1;j<=m;++j)A[i][j]=(s[j]=='*');
	}
	if(n<m){
		for(Re i=1;i<=n;++i)
			for(Re j=1;j<=m;++j)
				A_[j][i]=A[i][j];
		swap(n,m);
		for(Re i=1;i<=n;++i)
			for(Re j=1;j<=m;++j)
				A[i][j]=A_[i][j];
	}
	Mi[0]=1;for(Re i=1;i<=m+1;++i)Mi[i]=Mi[i-1]*3;
	V=Mi[m+1]-1,dp[o][0]=1;
	for(Re i=1;i<=n;++i){
		o^=1;
		for(Re s=0;s<=V;++s)dp[o][s]=s%3?0:dp[o^1][s/3];
		for(Re j=1;j<=m;++j){
			o^=1;
			for(Re s=0;s<=V;++s)dp[o][s]=0;
			for(Re s=0;s<=V;++s)if(dp[o^1][s]){
				Re L=s/Mi[j-1]%3,U=s/Mi[j+1-1]%3,ML=Mi[j-1],MU=Mi[j+1-1];
				if(A[i][j]){
					if(!L&&!U)mo(dp[o][s]+=dp[o^1][s]);
				}
				else{
					if(L==0&&U==0){
						mo(dp[o][s+ML]+=dp[o^1][s]);
						mo(dp[o][s+MU]+=dp[o^1][s]);
						mo(dp[o][s+2*ML+2*MU]+=dp[o^1][s]);
					}
					if(L==0&&U==1){
						mo(dp[o][s+MU]+=dp[o^1][s]);
						mo(dp[o][s+ML-MU]+=dp[o^1][s]);
					}
					if(L==0&&U==2){
						mo(dp[o][s+2*ML-2*MU]+=dp[o^1][s]);
						mo(dp[o][s-2*MU]+=dp[o^1][s]);
					}
					if(L==1&&U==0){
						mo(dp[o][s+ML]+=dp[o^1][s]);
						mo(dp[o][s-ML+MU]+=dp[o^1][s]);
					}
					if(L==1&&U==1)mo(dp[o][s-ML-MU]+=dp[o^1][s]);
					if(L==1&&U==2);
					if(L==2&&U==0){
						mo(dp[o][s-2*ML+2*MU]+=dp[o^1][s]);
						mo(dp[o][s-2*ML]+=dp[o^1][s]);
					}
					if(L==2&&U==1);
					if(L==2&&U==2);
				}
			}
		}
	}
	printf("%d\n",dp[o][0]);
}
已复制