状压dp + 最小割中inf双向单向变的捆绑决定技巧：ABC472G

法1：状压dp

首先本质上每一行都是可以抽象成连续段，连续段数量不超过15，所以每一维的状态可以直接存下来。

设 dp[i][S]dp[i][S] 代表第 ii 行的状态为 SS 时，前 ii 行的最大值。

显然对于一个固定的 SS，可以很轻松求出下一行对应的 S′S'，因此转移到 dp[i+1][S′]dp[i+1][S']。

而现在考虑新的一行的内部，可以新增#段。也就是让 dp[i+1][S]dp[i+1][S] 贡献到 dp[i+1][S\or 2^j] 中。

时间复杂度 O(n×2n)O(n\times 2^n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 35
int n, m, i, j, k, T; 
int a[1 << 16], c[N], b[N]; 
int f[N][1 << 16]; 
int s1, s, ans; 
char S[N][N]; 
 
int calc(int s, int i) {
	int j, k = 0, o; 
	for(j = 1; j <= m; ++j) b[j] = 0; 
	for(j = 1; j <= m; ++j) if(S[i - 1][j] != '#') {
		++k; 
		if(s & (1 << k - 1)) o = 1; else o = 0; 
		while(S[i - 1][j] != '#' && j <= m) {
			if(o) b[j] = 1; 
			++j; 
		}
		--j; 
	}
	for(j = 1; j <= m; ++j) 
		if(b[j] && S[i][j] == '#') b[j] = 0; 
	for(j = 1; j <= m; ++j) if(b[j]) {
		while(j > 1 && !b[j - 1] && S[i][j - 1] != '#')
			--j, b[j] = 1; 
		while(j < m && !b[j + 1] && S[i][j + 1] != '#')
			++j, b[j] = 1; 
	}
	int ans = 0; 
	for(j = 1, k = 0; j <= m; ++j) if(S[i][j] != '#') {
		++k; if(b[j]) ans |= (1 << k - 1); 
		while(S[i][j] != '#' && j <= m) ++j; --j; 
	}
	return ans; 
}   

signed main() {
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T = read();
//	while(T--) {
//
//	}
	n = read(); m = read(); 
	for(i = 1; i <= n; ++i) scanf("%s", S[i] + 1); 
	for(i = 1; i <= n; ++i) {
		for(s = 0; s < (1 << 15); ++s) f[i][s] = -1e9; 
		for(k = 0; k < 15; ++k) c[k] = 0; 
		for(s = 0; s < (1 << 15); ++s) {
			a[s] = 0; 
			for(j = 1, k = 0; j <= m; ++j) if(S[i][j] != '#') {
				int cnt = 0; 
				while(S[i][j] != '#' && j <= m) 
					cnt += (S[i][j] == '+' ? 1 : -1), ++j;
				++k; --j; c[k - 1] = cnt; 
				if(!(s & (1 << k - 1))) a[s] += cnt; 
			}
		}
		int mx = k; debug(">> %d\n", mx); 
		for(k = 0; k < mx; ++k) debug("%d ", c[k]); debug("%d\n"); 
		for(s = 0; s < (1 << 15); ++s) {
			s1 = calc(s, i); 
			f[i][s1] = max(f[i][s1], f[i - 1][s] + a[s1]); 
		}
		for(s = 0; s < (1 << 15); ++s) {
			for(k = 0; k < mx; ++k) if(s & (1 << k)) {
				int ss = s - (1 << k); 
				f[i][s] = max(f[i][s], f[i][ss] - c[k]); 
			}
		} 
	}
	for(s = 0; s < (1 << 15); ++s) ans = max(ans, f[n][s]); 
	printf("%d", ans); 
	return 0;
}



法2： 最小割

我们可以发现一些性质：

  • 如果一个点是空格，那样子它的左右必然是空格
  • 如果一个点是空格，那么它的上面必然是空格

我们可以假设我们把所有的+都不变，所有的-都是#。

然后我们现在要开始反悔了。反悔是有代价的，所以我们考虑让这个代价最小。

我们考虑最小割。

所有点和S、T都相连。如果最终和S相连代表它不变，如果最终和T相连，代表变成#。

如果最后+和T相连，答案要-1，所以这个+和S这条边的权值是1。

-还是-的话，即和S相连，答案也要-1，这个-和T相连的权值也为1。

然后我们还要满足题目条件的限制：

  • 若左右相邻，说明二者的状态必须一致，所以我们连inf的双向边
  • 如果上下相邻，说明下是空地时，上一定也是空地，所以我们从下往上连一条inf的单向边

image-20260906084025453

跑最小割即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
#include<atcoder/all> 
using namespace std;
using namespace atcoder; 
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 35
int n, m, i, j, k, T;
int ans, S; 
char s[N][N]; 

signed main() {
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T = read();
//	while(T--) {
//
//	}
	n = read(); m = read(); 
	mf_graph<int>G(n * m + 2); S = 0; T = n * m + 1; 
	for(i = 1; i <= n; ++i) scanf("%s", s[i] + 1); 
	auto zh = [&] (int x, int y) -> int {
		return (x - 1) * m + y; 
	}; 
	for(i = 1; i <= n; ++i) 
		for(j = 1; j <= m; ++j) {
			if(s[i][j] == '#') continue; 
			if(s[i][j] == '+') ++ans; 
			if(s[i][j] == '+') 
				G.add_edge(S, zh(i, j), 1); 
			if(s[i][j] == '-')
				G.add_edge(zh(i, j), T, 1); 
			if(j < m && s[i][j + 1] != '#') {
				G.add_edge(zh(i, j), zh(i, j + 1), 1e9); 
				G.add_edge(zh(i, j + 1), zh(i, j), 1e9); 
			}
			if(i > 1 && s[i - 1][j] != '#') {
				G.add_edge(zh(i, j), zh(i - 1, j), 1e9); 
			}
		}
	ans -= G.flow(S, T); 
	printf("%d", ans); 
	return 0;
}