#插头dp#洛谷 5074 Eat the Trees

题目

给出 (n*m) 的方格，有些格子不能铺线，

其它格子必须铺，可以形成多个闭合回路。

问有多少种铺法？ (n,mleq 12)

---

分析

设 (dp[n][m][S][0/1]) 表示处理到 ((n,m))，
目前插头的状态为 (S)，并且左边的插头是否向右暴露，
插头的状态指的是轮廓线上的插头是否向下暴露，这个分类讨论一下就可以了，
注意到右边界的位置不能向右暴露，并且不能铺线的地方要继续更新方案

---

代码

#include <cstdio>
#include <cctype>
#include <cstring>
#define rr register
using namespace std;
int n,m,al,a[12][12];
long long dp[4101][2],f[4101][2];
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
signed main(){
	for (rr int T=iut();T;--T){
		memset(dp,0,sizeof(dp));
	    n=iut(),m=iut(),al=1<<m,dp[0][0]=1;
		for (rr int i=0;i<n;++i)
		for (rr int j=0;j<m;++j)
		    a[i][j]=iut();
		for (rr int i=0;i<n;++i)
		for (rr int j=0;j<m;++j){
			if (a[i][j]){
				for (rr int k=0;k<al;++k)
				if ((k>>j)&1){
					f[k][0]+=dp[k][0];
					f[k^(1<<j)][1]+=dp[k][0];
					f[k^(1<<j)][0]+=dp[k][1];
				}else{
					f[k][1]+=dp[k][1];
					f[k|(1<<j)][0]+=dp[k][1];
					f[k|(1<<j)][1]+=dp[k][0]; 
				}
			}else{
				for (rr int k=0;k<al;++k)
				if (!((k>>j)&1))
				    f[k][0]=dp[k][0];
			}
			if (j==m-1){
				for (rr int k=0;k<al;++k)
				    f[k][1]=0;
			} 
			memcpy(dp,f,sizeof(dp));
			memset(f,0,sizeof(f));
		}
		printf("%lld
",dp[0][0]);
	}
	return 0;
}