LCP04-覆盖

  |  

摘要: LCP04,状态压缩DP和二分图匹配两种解法

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


今天我们来看一个比较难的图论题,力扣 LCP04。有状态压缩 DP 和二分图最大权匹配两种解法。之前还有另一个题 【DP难题】力扣1595-连通两组点的最小成本 也是状态压缩 DP 和二分图最大权匹配两种解法。可以对比着看。

题目

你有一块棋盘,棋盘上有一些格子已经坏掉了。你还有无穷块大小为1 * 2的多米诺骨牌,你想把这些骨牌不重叠地覆盖在完好的格子上,请找出你最多能在棋盘上放多少块骨牌?这些骨牌可以横着或者竖着放。

输入:n, m代表棋盘的大小;broken是一个b * 2的二维数组,其中每个元素代表棋盘上每一个坏掉的格子的位置。

输出:一个整数,代表最多能在棋盘上放的骨牌数。

1
2
3
4
限制:
1 <= n <= 8
1 <= m <= 8
0 <= b <= n * m

示例 1:
输入:n = 2, m = 3, broken = [[1, 0], [1, 1]]
输出:2
解释:我们最多可以放两块骨牌:[[0, 0], [0, 1]]以及[[0, 2], [1, 2]]。(见下图)

示例 2:
输入:n = 3, m = 3, broken = []
输出:4
解释:下图是其中一种可行的摆放方式


题解

算法1: 二分图匹配

二分图匹配有两个要点

  • 节点能分成独立的两个集合,每个集合内部有 0 条边。
  • 每个节点只能与 1 条匹配的边相连

把实际问题抽象成二分图匹配问题时,要寻找具有以上两条性质的对象。

本题中,任意两张骨牌不重叠,也就是每个格子只能被一张骨牌覆盖,与要点 2 对应。而骨牌大小是 1 * 2,与要点 1 对应。因此,我们可以把棋盘上未被禁止的各自作为节点,骨牌作为无向边。

建图之后,用匈牙利算法进行二分图最大匹配。

在文章 二分图匹配-最大匹配 中,有关于匈牙利算法的详细阐述。

代码(C++)

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
class Solution {
public:
int domino(int n, int m, vector<vector<int>>& broken) {
int n_broken = broken.size();
vector<vector<int>> g(n * m);
unordered_set<int> setting;
for(const vector<int>& b: broken)
setting.insert(key(b[0], b[1], m));
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
{
int u = key(i, j, m);
if(setting.count(u) > 0)
continue;
for(int d = 0; d < 4; ++d)
{
int x = i + dx[d];
int y = j + dy[d];
if(x < 0 || x >= n || y < 0 || y >= m)
continue;
int v = key(x, y, m);
if(setting.count(v) > 0)
continue;
g[u].push_back(v);
}
}
int ans = 0;
vector<bool> visited;
vector<int> match(n * m, -1);
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
{
int u = key(i, j, m);
if(setting.count(u) > 0)
continue;
visited.assign(n * m, false);
visited[u] = true;
if(dfs(u, g, visited, match))
++ans;
}
return ans / 2;
}

bool dfs(int u, const vector<vector<int>>& g, vector<bool>& visited, vector<int>& match)
{
for(int v: g[u])
{
if(visited[v])
continue;
visited[v] = true;
if(match[v] == -1 || dfs(match[v], g, visited, match))
{
match[v] = u;
return true;
}
}
return false;
}

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int key(int x, int y, int m)
{
return x * m + y;
}
};

算法2: 状态压缩DP

在文章 状态压缩DP 中,我们用状态压缩 DP 解决过类似的问题,本题有两个变化:

  1. 多了障碍点
  2. 问有多少种铺满方案改成了最多放多少骨牌

考虑以某一行为界,将棋盘分成上下两部分。

假设前 i - 1 行已经摆放好,考虑第 i 行的各个位置,如果某个位置(第 j 列)的前一行是竖着的骨牌的上半部分,则该部分必须补全该骨牌而无法放新骨牌,如果该位置为障碍点,则该位置也无法放新骨牌。其余情况则该位置可以放置新骨牌。

也就是说,当 (i, j) 位置出现以下两种情况之一,则该位置无法放置新骨牌

  1. (i, j) 位置是障碍点
  2. (i - 1, j) 放置了一块竖着的骨牌

因此,可以把行号作为 DP 的阶段,把上半部分不断向下扩展,直至确定整个棋盘。

为了描述第 i 行的可放新骨牌的位置的详细形态,用一个 m 位二进制数,其中第 j 位为 0 表示 (i, j) 不能放置新骨牌;为 1 表示可以放置新骨牌。

当第 i 行的状态为 s 的时候,考察所有可以放骨牌的位置(s >> j & 1 为 1 的位置),有三种可能的选择

  1. 不放置
  2. 竖着放置,此时会影响到下一行
  3. 横着放置

枚举所有可竖着放置位置组成的集合的子集,对子集中的位置竖着放置,剩余位置尽可能多地横着放置,此时第 i 行就放置完了,即可将阶段从 i 推进到 i + 1,考察第 i + 1 行的状态。

完整算法如下

1
2
3
4
5
6
7
8
9
10
11
12
状态定义
dp[i][s] := 表示第 i 行的形态为 s 的时候,第 i 行到第 n 行(最后一行下面假想的一行)的方案总数

答案
dp[0][(~b[0]) & mask]

初始化
dp[n][s] = 0

状态转移
dp[i][s] = max(竖着放置的数目 + 横着放置的数目 + dp[i + 1][(~(t | b[i + 1])) & mask])
其中 t 是 s 的子集,且 (t & b[i + 1]) = 0

其中:

  • b[i] 表示第 i 行障碍点的情况,(b[i] >> j & 1) 为 1 表示 (i, j) 为障碍点。
  • mask 为 (1 << m) - 1

dp[n][s] 表示的是棋盘最后一行下面假想的一行,这一行视为全都是障碍点,这样处理比较好写。

代码(C++)

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
class Solution {
public:
int domino(int n, int m, vector<vector<int>>& broken) {
mask = (1 << m) - 1;
vector<int> b(n + 1, 0);
b[n] = mask;
for(const vector<int>& broken_point: broken)
{
int i = broken_point[0];
int j = broken_point[1];
b[i] |= (1 << j);
}
vector<vector<int>> dp(n + 1, vector<int>(1 << m, -1));
for(int s = 0; s < (1 << m); ++s)
dp[n][s] = 0;
return solve(0, (~b[0]) & mask, b, dp);
}

int mask;

int solve(int i, int s, const vector<int>& b, vector<vector<int>>& dp)
{
if(dp[i][s] != -1)
return dp[i][s];
dp[i][s] = 0;
for(int t = s; ; t = (t - 1) & s)
{
if((t & b[i + 1]) != 0)
continue;
int n1 = check1(t); // 竖着放的个数
int n2 = check2(s & (~t)); // 横着放的个数
dp[i][s] = max(dp[i][s], n1 + n2 + solve(i + 1, (~(t | b[i + 1])) & mask, b, dp));
if(t == 0)
break;
}
return dp[i][s];
}

int check2(int x)
{
// x 中长度为 2 的连续 1 的个数
int n = 0;
while(x > 0)
{
while(x > 0 && (x & 1) == 0)
x >>= 1;
x >>= 1;
if((x & 1) == 1)
{
x >>= 1;
++n;
}
}
return n;
}

int check1(int x)
{
// x 中 1 的个数
int n = 0;
while(x > 0)
{
if((x & 1) == 1)
++n;
x >>= 1;
}
return n;
}
};

Share