自动搬运

查看原文

来自洛谷，原作者为

	小粉兔 Always continue; Never break;

搬运于2025-08-24 22:06:50，当前版本为作者最后更新于2018-12-17 18:47:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

插头 DP 简单题，不需要括号序列。

滚动数组，每次从 f 转移到 g。

每次考虑当前方格下方和右方的插头，看从左方和上方的什么状态转移过来：
00 从 11 转移，01 从 01 和 10 转移，10 从 01 和 10 转移，11 从 00 转移。

写成位运算的形式就是 g[b]=f[b^3<<j]+((b>>j&1)^(b>>j+1&1)?f[b]:0)，b 是状态。

要注意行末/初的时候要对状态进行移位的特殊处理。开 long long。

复杂度 $\Theta(nm2^{m+1})$。

#include<cstdio>
#define F(i,n) for(int i=0;i<n;++i)
int T,n,m,s,c[12][12];
long long f[1<<13],g[1<<13];
int main(){
	for(scanf("%d",&T);T--;){
		scanf("%d%d",&n,&m);s=1<<m+1;
		F(i,n)F(j,m)scanf("%d",&c[i][j]);
		F(i,s)g[i]=0;g[0]=1;
		F(i,n)F(j,m){
			F(b,s)f[b]=j?g[b]:b&1?0:g[b>>1];
			if(!c[i][j])F(b,s)g[b]=b>>j&3?0:f[b];
			else F(b,s)g[b]=f[b^3<<j]+((b>>j&1)^(b>>j+1&1)?f[b]:0);
		}printf("%lld\n",g[0]);
	}
	return 0;
}