夏晓光(loveJY)的博客

国家队队长李佳衡推荐插头DP练习题

$Orzljh$

不过这个题经过兔队之手真的好简单的样子啊

直接设计状态f[S],S的0/1表示轮廓线上这一位有没有插头

然后考虑继承前一个状态?直接右移1

然后分类讨论吧

考虑上面和左边的是0还是1

case1: 11

那么我们只能把他们在这个合成一个,不能向下右转移,00

case2:10

右边可以随便延伸或者停止,10,01,00

case3:01

好像和case2一样啊

case3:00

好像除了不铺线可以自由发挥啊,也就是说我们可以转移到10,01,11

总结一下,如果为00那我们可以转移到他某位异或

如果已获知为1可以转移到00和异或一样的

11只能转移00

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
int T, n, m, s, c[12][12];
ll f[1 << 13], g[1 << 13];
int main() {
	for(scanf("%d", &T); T--;) {
		scanf("%d%d", &n, &m);
		s = (1 << m + 1);
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < m; ++j) {
				scanf("%d", &c[i][j]);
			}
		}
		for(int i = 0; i < s; ++i)g[i] = 0;
		g[0] = 1;
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < m; ++j) {
				for(int k = 0; k < s; ++k)
					f[k] = j ? g[k] : (k & 1 ? 0 : g[k >> 1]);//滚动数组

				if(!c[i][j])
					for(int k = 0; k < s; ++k)g[k] = k >> j & 3 ? 0 : f[k];//不能铺线,最后一定由0,0转移来
				else
					for(int k = 0; k < s; ++k)g[k] = f[k ^ 3 << j] + ((k >> j & 1) ^ (k >> j + 1 & 1) ? f[k] : 0);//不一样可以再一个转移
				//这个是直接做,考虑总结规律?
			}
		}
		printf("%lld\n", g[0]);//有一个插头都不行
	}
	return 0;
}