这里默认各位都会轮廓线 dp。

引入

题意:给出 \(n\times m\) 的方格,有些格子不能铺线,其它格子必须铺,可以形成多个闭合回路。问有多少种铺法?

\(2\le n,m\le 12\)

考虑如果每个格子和相邻格子(包括边缘)的衔接都合法,最终一定能形成若干个闭合回路,因此我们只需要在这个条件上 dp。

\(f[i,j,S]\) 表示到达 \((i,j)\) 时上方的轮廓线状态是 \(S\) 的方案数。

这里,我们称轮廓线中向下的延伸和当前格子左侧向右的延伸叫作 插头

每次填的格子有六种可能:

然后分类讨论上面和左边分别有没有插头。

  • 都没有:当前格子必须往右边和下面各延伸一个插头

  • 上面有:可以把上面的插头向下延伸,或者拐弯向右延伸

  • 左边有:可以把左边的插头向右延伸,或者拐弯向下延伸

  • 都有:把这两个插头合并

点击查看代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define mkp make_pair
#define fi first
#define se second
#define pir pair<ll,ll>
#define pb push_back
using namespace std;
const ll maxn=13;
ll t,n,m,f[maxn*maxn][1<<12][2],lim;
void ad(ll &x,const ll &y) {x+=y;}
int main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld",&n,&m); lim=(1<<m)-1;
		memset(f,0,sizeof f);
		f[0][0][0]=1;
		for(ll i=1;i<=n;i++){
			for(ll j=1;j<=m;j++){
				ll x=(i-1)*m+j, w; scanf("%lld",&w);
				for(ll S=0;S<=lim;S++){
					if(w){
						if(S&(1<<m-1)){
							ad(f[x][(S<<1)&lim|1][0],f[x-1][S][0]);
							ad(f[x][(S<<1)&lim][0],f[x-1][S][1]);
							if(j<m) ad(f[x][(S<<1)&lim][1],f[x-1][S][0]);
						} else{
							if(j<m) ad(f[x][S<<1][1],f[x-1][S][1]);
							ad(f[x][S<<1|1][0],f[x-1][S][1]);
							if(j<m) ad(f[x][S<<1|1][1],f[x-1][S][0]);
						}
					} else{
						if(!(S&(1<<m-1))){
							ad(f[x][S<<1][0],f[x-1][S][0]);
						}
					}
				}
			}
		}
		printf("%lld\n",f[n*m][0][0]);
	}
	return 0;
}

问题

题意:给出 \(n\times m\) 的方格,有些格子不能铺线,其它格子必须铺,形成一个闭合回路。问有多少种铺法?

\(2\le n,m\le 12\)

这和上题唯一的区别在于必须恰好形成一个闭合回路。

每次维护的 \(S\) 包括左边的插头,是一个插头集合,我们可以多加一点信息来表示所有插头的连通性情况。

具体的,用最小表示法来表示一个插头连通性状态,然后哈希映射到一个较小的整数状态上。

但是还有更好的方法。如果算上左边的插头,我们把插头集合按 \(1\sim m\)(左边的插头所处位置是一个缝隙)的位置顺序来观察,会发现他们的连通性恰好形成一个括号序列。

具体的,比如:

\[\text{()(()())} \]

\[\text{1 2 3 4 5 6 7 8} \]

那么第 \(1\) 个和 第 \(2\) 个插头连通,第 \(3\) 个和 第 \(8\) 个插头连通,第 \(6\) 个和第 \(7\) 个插头连通。

所以我们可以用一个三进制数来表示状态,分别表示 无插头/左括号/右括号。

\(p_1,p_2\) 分别表示左边和上方位置的单个位置的状态,分类讨论:

  • \(p_1=p_2=0\):我们需要新开两个插头,一个向右,一个向下。

  • \(p_1=0,p_2>0\):此时只有上方有插头,可以继续向下延伸,也可以拐弯向右。

  • \(p_1>0,p_2=0\):此时只有左边有插头,可以继续向右延伸,也可以拐弯向下。

  • \(p_1=p_2=1\):两个都是“左括号”插头。合并后长这样:

会发现蓝色和绿色的右括号连通,可以视绿色的右括号为左括号。

具体的,我们向后找到匹配上插头的右括号,变为左括号。

  • \(p_1=1,p_2=2\):由于两个插头早已连通,此时合并完后会形成一个完整的回路,判断当前格子是否为 \((n,m)\),只有在 \((n,m)\) 时才会合并出这样一个回路

  • \(p_1=2,p_2=1\):直接合并。

  • \(p_1=p_2=2\):类似于 \(p_1=p_2=1\) 的情况,我们向前面找到匹配左插头的左括号,变成右括号。

然后状态数是严重不满的,我们考虑使用哈希表存下所有有用状态,或者 unordered_map。

那么现在的时间就和有用状态有关了。为了方便,可以用四进制数代替三进制数。

点击查看代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define mkp make_pair
#define fi first
#define se second
#define pir pair<ll,ll>
#define pb push_back
using namespace std;
const ll maxn=20, M=3e5+10;
ll n,m,z,tot[2],st[2][M],f[2][M],bit[maxn],ex,ey,ans,b[maxn][maxn];
char a[maxn][maxn];
struct hash_table{
	ll hd[M],nxt[M];
	void ins(ll x,ll v){
		ll p=x%299993+1;
		for(ll i=hd[p];i;i=nxt[i])
			if(st[z][i]==x){
				f[z][i]+=v; return;
			}
		nxt[++tot[z]]=hd[p], hd[p]=tot[z];
		st[z][hd[p]]=x, f[z][hd[p]]=v;
	}
	void clr(){
		memset(hd,0,sizeof hd);
		tot[z]=0;
	}
}H;
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++){
		scanf("%s",a[i]+1);
		for(ll j=1;j<=m;j++){
			if(a[i][j]=='.') ex=i, ey=j;
			b[i][j]=(a[i][j]=='.');
		}
	}
	bit[1]=1;
	for(ll i=2;i<=m+1;i++) bit[i]=bit[i-1]<<2;
	H.ins(0,1);
	for(ll i=1;i<=n;i++){
		for(ll j=1;j<=tot[z];j++) st[z][j]<<=2;
		for(ll j=1;j<=m;j++){
			z^=1, H.clr();
			for(ll k=1;k<=tot[z^1];k++){
				ll msk=st[z^1][k], val=f[z^1][k], p1=(msk>>(j-1<<1))&3, p2=(msk>>(j<<1))&3;
				if(a[i][j]=='*'){
					if(!p1&&!p2) H.ins(msk,val);
				} else{
					if(!p1&&!p2&&b[i][j+1]&&b[i+1][j]) H.ins(msk+bit[j]+2*bit[j+1],val);
					if(!p1&&p2){
						if(b[i][j+1]) H.ins(msk,val);
						if(b[i+1][j]) H.ins(msk-p2*bit[j+1]+p2*bit[j],val);
					}
					if(p1&&!p2){
						if(b[i+1][j]) H.ins(msk,val);
						if(b[i][j+1]) H.ins(msk-p1*bit[j]+p1*bit[j+1],val);
					}
					if(p1==1&&p2==1){
						ll c=1;
						for(ll r=j+2;r<=m+1;r++){
							ll x=(msk>>(r-1<<1))&3;
							if(x==1) ++c;
							if(x==2) --c;
							if(!c){
								H.ins(msk-bit[j]-bit[j+1]-bit[r],val);
								break;
							}
						}
					}
					if(p1==1&&p2==2){
						if(i==ex&&j==ey) ans+=val;
					}
					if(p1==2&&p2==1) H.ins(msk-2*bit[j]-bit[j+1],val);
					if(p1==2&&p2==2){
						ll c=1;
						for(ll r=j-1;r;r--){
							ll x=(msk>>(r-1<<1))&3;
							if(x==2) ++c;
							if(x==1) --c;
							if(!c){
								H.ins(msk-2*(bit[j]+bit[j+1])+bit[r],val);
								break;
							}
						}
					}
				}
			}
		}
	}
	printf("%lld",ans);
	return 0;
}

例题

题意:求一个最大闭合简单回路,满足回路上所有格子的权值总和最大,求最大值。

\(2\le n\le 100,\space 2\le m\le 6\)

直接把方案数换成最大值即可。

有一些细节要注意。这里不要求回路包含每个格子,因此可以对两个插头都没有的情况置之不理。每个格子都可以算总答案,判断条件是当前插头集合中只有合并的这两个插头。

题意:一个人,从 \((1,1)\) 开始需要经过 \((1\sim n,1\sim m)\) 所有点,最后回到 \((1,1)\)。每次在相邻点之间移动,求有多少种最短路径。

直接求回路个数。

特判 \(n=1\)\(m=1\) 的情况,此时可以重复经过点,答案是 \(1\)

声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。