【luogu P5056】【模板】插头dp(插头DP)(分类讨论)

2022/9/2 23:24:57

本文主要是介绍【luogu P5056】【模板】插头dp(插头DP)(分类讨论),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

【模板】插头dp

题目链接:luogu P5056

题目大意

有一个 n*m 的网格,每个格子要么必须铺线,要么必须不铺。
然后问你有多少个铺发使得形成一个闭合回路。

思路

快乐插头 DP 模板题。

首先默认都会插头 DP,其实不会也没啥,其实就是你压你当前处理的位置跟没处理的分界线(一般叫轮廓线)。
所以主要的问题是如何压状态,因为似乎直接用这个位置是否有线不太能表示出对于的状态,它们之间还有连通关系。

那考虑是怎样连通的,自然是两两对着的,而且因为是闭合回路,自然是不会出现交叉的,所以有一个东西叫做括号序列就跟这个东西对应上了。
然后你就把左括号变成 \(1\),右括号变成 \(2\),如果是不铺的就是 \(0\)。
然后为了快速以及方便其实我们可以把它弄成 \(2^2=4\) 进制的。

于是我们考虑分类的讨论:
首先不能铺的格子就不铺啊,那就必须是 \(00\),下面默认能铺。

\(00\):就只能右跟下,因为一定要铺,所以变成了 \(12\)。
\(01\):那就续上这条线段,续到右边 \(01\) 或者下面 \(10\) 都行。
自然 \(02,10,20\) 同理,就是续。
\(11\):看起来一定要接上,但是又不能接上,似乎矛盾了。于是考虑把后面那个改成 \(2\),这样不会重复因为这个 \(2\) 只有这样才会诞生。那这个改成 \(2\) 你就相当于把后面的 \(1\) 对于的 \(2\) 去掉变成 \(0\),这个你直接往后扫 \(O(n)\) 找没问题的。
\(22\):跟 \(11\) 一样的道理,不过这次你是找前面跟第一个 \(2\) 匹配的 \(1\) 把它变成 \(0\)。
\(21\):这个就直接接上,变成 \(00\) 即可。
\(12\):这个就是最后一步把环合上,自然只能在最后一个点出现,在这里统计入答案即可。

然后是一些注意事项:

  1. 这个最后一步不一定是右下方,因为可能那里不能铺,要找的是最后一个能铺的位置。
  2. 自然要滚动数组,毕竟状态数不少。
  3. 发现直接搞状态时还是太多了,但是插头 DP 特有的有用状态少使得我们可以试着只把有用的状态找出来。
    但是你怎么对应上呢?那就用哈希吧!
    不过感觉这里邻接表样子的哈希不如往后移找位置的。(个人感觉,所以写的是后者)
  4. 注意换到新的一行,轮廓写一列的那个位置从最后变回到了最前,记得把之前的状态改一下。
    因为我这里状态是按顺序压的,当然你也可以把特殊的那个一列的轮廓一直放在 \(0\) 的位置也不是不行。

代码

#include<cstdio>
#include<cstring> 
#define ll long long
#define ull unsigned long long

using namespace std;

const int N = 13;
const int S = 1e5 + 100;
const int HS = 100003;
int n, m, tot[2], _, hash[HS], ex, ey;
bool in[N][N];
ll f[2][S], fv[2][S], ans;

void add(ll S, ll va) {
	int x = S % HS;
	while (hash[x]) {
		if (fv[_][hash[x]] == S) {
			f[_][hash[x]] += va; return ;
		}
		x = (x + 1) % HS;
	}
	hash[x] = ++tot[_]; fv[_][hash[x]] = S; f[_][hash[x]] = va;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			char c = getchar(); while (c != '*' && c != '.') c = getchar();
			if (c == '.') in[i][j] = 1, ex = i, ey = j;
		}
	
	tot[0] = 1; f[0][1] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			_ ^= 1;
			tot[_] = 0; memset(hash, 0, sizeof(hash));
			for (int k = 1; k <= tot[_ ^ 1]; k++) {
				ll S = fv[_ ^ 1][k];
				ll l = (S >> ((j - 1) << 1)) & 3;
				ll r = (S >> (j << 1)) & 3;
				if (!in[i][j]) {
					if (!l && !r) add(S, f[_ ^ 1][k]);
					continue;
				}
				if (!l && !r) {
					if (!in[i][j + 1] || !in[i + 1][j]) continue;
					add(S ^ (1 << ((j - 1) << 1)) ^ (2 << (j << 1)), f[_ ^ 1][k]);
				}
				if (!l && r) {
					if (in[i + 1][j]) add(S ^ (r << (j << 1)) ^ (r << ((j - 1) << 1)), f[_ ^ 1][k]);
					if (in[i][j + 1]) add(S, f[_ ^ 1][k]);
				}
				if (l && !r) {
					if (in[i + 1][j]) add(S, f[_ ^ 1][k]);
					if (in[i][j + 1]) add(S ^ (l << ((j - 1) << 1)) ^ (l << (j << 1)), f[_ ^ 1][k]);
				}
				if (l == 1 && r == 1) {
					int num = 0;
					for (int o = j + 1; o <= m; o++) {
						if (((S >> (o << 1)) & 3) == 1) num++;
							else if (((S >> (o << 1)) & 3) == 2) num--;
						if (num < 0) {
							add(S ^ (1 << ((j - 1) << 1)) ^ (1 << (j << 1)) ^ (2 << (o << 1)) ^ (1 << (o << 1)), f[_ ^ 1][k]);
							break;
						}
//						if (o == m) {
//							while (1) {
//								ans++;
//							}
//						}
					}
				}
				if (l == 2 && r == 2) {
					int num = 0;
					for (int o = j - 2; o >= 0; o--) {
						if (((S >> (o << 1)) & 3) == 1) num--;
							else if (((S >> (o << 1)) & 3) == 2) num++;
						if (num < 0) {
							add(S ^ (2 << ((j - 1) << 1)) ^ (2 << (j << 1)) ^ (1 << (o << 1)) ^ (2 << (o << 1)), f[_ ^ 1][k]);
							break;
						}
//						if (o == 0) {
//							while (1) {
//								ans++;
//							}
//						}
					}
				}
				if (l == 2 && r == 1) {
					add(S ^ (2 << ((j - 1) << 1)) ^ (1 << (j << 1)), f[_ ^ 1][k]);
				}
				if (l == 1 && r == 2) {
					if (i == ex && j == ey) ans += f[_ ^ 1][k];
				}
			}
		}
		for (int j = 1; j <= tot[_]; j++) fv[_][j] <<= 2;//把跑到最右边的状态移会最左边 
	}
	
	printf("%lld", ans);
	
	return 0;
}


这篇关于【luogu P5056】【模板】插头dp(插头DP)(分类讨论)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程