P4262 [Code+#3]白金元首与莫斯科

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

不用多说啥吧qwq ,元首 $Adolf$ 永在qwq

1*2多米诺骨牌合法放置方案数,存在基础障碍位置
你需要确定n*m每个位置额外成为障碍时的答案

一看就很自闭,所以我们考虑枚举每个位置是否为障碍

然后设计下状态, $f[i][j][S]$ 表示我目前在(i,j),长度为i+1的轮廓线插头状态

如果这个线是横的,那么1是下插头,0为没有插头
如果这个线是竖的,那么1是右插头,0是没

eg:

然后考虑转移

case1:这个格子是个障碍

只有在都没有插头的时候才能转移

case2:这个格子健全,但是同时有下和右插头

命没了

case3:只有右插头||只有下插头

转移后竖线和这个横线都变成没插头状态

case4:没插头

如果右边不是障碍,那么可以右,同理可以放下

当然,也可以空出这个格子qwq

然后...好像没啥了啊

等等,你发现他TLE了

那么我们考虑优化枚举每个点的过程,我们从下到上和刚刚完全反着的做一遍,就可以通过上DP数组和下DP数组来拼出每个点做障碍的答案

具体的,枚举到的点(i,j)只有 $f[i][j][S]$ , $g[i][j][k]$ 的S和K都没有插头才能乘起来

code:

#include<iostream>
#include<cstdio>
#include<cstring>
const int MAXN = 18;
const int P = 1e9 + 7;
using namespace std;
int n, m, ma[20][20];
int f[MAXN][MAXN][270000];
int g[MAXN][MAXN][270000];
int ans[20][20];

void modify(int &a, int b) {
	a += b;
	if(a > P)a -= P;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			scanf("%d", &ma[i][j]);
			ma[i][j] ^= 1;
            //强行^1
		}
	}
	int max_state = (1 << m + 1) - 1;
	f[0][m][0] = 1;
	for(int i = 1; i <= n; ++i) {
		for(int j = 0; j <= max_state; ++j) {
			modify(f[i][0][j << 1], f[i - 1][m][j]);
		}
		for(int j = 1; j <= m; ++j) {
			for(int k = 0; k <= max_state; ++k) {
				int val = f[i][j - 1][k];
				if(!val)continue;
				int pl1 = (k >> j - 1) & 1;
				int pl2 = (k >> j) & 1;
				if(!ma[i][j]) {
					if(!pl1 && !pl2)modify(f[i][j][k], val);
					//case 1,障碍
				} else if(!pl1 && !pl2) {
					modify(f[i][j][k], val);
					//case 4,不放
					if(ma[i + 1][j])modify(f[i][j][k ^ (1 << j - 1)], val);//放右插头
					if(ma[i][j + 1])modify(f[i][j][k ^ (1 << j)], val);
                    //放下插头
				} else if(!pl1 && pl2) {
					modify(f[i][j][k ^ (1 << j)], val);
                    //只能放个空了,这个是为了去掉
				} else if(pl1 && !pl2) {
					modify(f[i][j][k ^ (1 << j - 1)], val);
				}

			}
		}
	}
	g[n + 1][1][0] = 1;
	for(int i = n; i > 0; --i) {//反着
		for(int j = 0; j <= max_state; ++j)modify(g[i][m + 1][j >> 1], g[i + 1][1][j]);
		for(int j = m; j > 0; --j) {//反着
			for(int k = 0; k <= max_state; ++k) {
				int val = g[i][j + 1][k];
                //从+1推
				if(!val)continue;
				int pl1 = (k >> j - 1) & 1;
				int pl2 = (k >> j) & 1;
				if(!ma[i][j]) {
					if(!pl1 && !pl2)modify(g[i][j][k], val);
				} else if(!pl1 && !pl2) {
					modify(g[i][j][k], val);
					if(ma[i - 1][j])modify(g[i][j][k ^ (1 << j)], val);
					if(ma[i][j - 1])modify(g[i][j][k ^ (1 << j - 1)], val);
				} else if(!pl1 && pl2) {
					modify(g[i][j][k ^ (1 << j)], val);
				} else if(pl1 && !pl2)
					modify(g[i][j][k ^ (1 << j - 1)], val);
			}
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			if(!ma[i][j])continue;
			int now = max_state ^ (1 << j - 1) ^ (1 << j);
			for(int k = now; k; k = (k - 1)&now)//调用子集即可
				modify(ans[i][j], 1ll * f[i][j - 1][k] * g[i][j + 1][k] % P);
                //显然可以组合,当且仅当他们是一样的
			modify(ans[i][j], 1ll * f[i][j - 1][0]*g[i][j + 1][0] % P);
            //0也是好选择,减子集弄不到0
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			printf("%d ", ans[i][j]);
		}
		puts("");
	}
	return 0;
}

唉,学OI的热情下降?我博客图都很慢更新了

夏晓光(loveJY)的博客

CF575I Robots protection