313.DOMINO

算法思路

1. 问题分析

本问题要求在 n×n 网格上放置 k 个 1×2 骨牌，覆盖数值较大的单元格，使剩余单元格和最小。等价于选择 k 个不相交骨牌，使覆盖值之和最大，再用总和减去该最大值。

关键点：

• 网格规模大（n ≤ 2000），但 k 值小（≤8）
• 骨牌覆盖值 = 两单元格值之和
• 骨牌不能重叠（即无公共单元格）

2. 解决策略

1. 预处理：

   • 计算网格总和
   • 收集所有相邻单元格对（横向/纵向）作为候选骨牌
   • 保留值最大的 50 个骨牌（贪心剪枝）

2. 分组处理：

   • 组 A：前 d 个骨牌（d = min(50, 21)）
   • 组 B：剩余骨牌

3. 组 A 状态压缩 DP：

   • 状态 f[s]：组 A 中选取骨牌集合 s 的最大覆盖值
   • 处理冲突：若两骨牌共享单元格，则不能同时选取

4. 组 B 组合枚举：

   • 枚举组 B 中选取 t (0≤t≤k) 个骨牌的组合
   • 预处理冲突关系：
     • conflictB：组 B 内部骨牌冲突掩码
     • gstB：组 B 骨牌与组 A 的冲突掩码
   • dp_g[state][t]：在组 A 状态掩码 state 下，组 B 选 t 个骨牌的最大值

5. 子集动态规划：

   • 对 dp_g 做子集传递：dp_g[state][t] = max(dp_g[state][t], dp_g[state|(1<<i)][t])

6. 合并结果：

   • 枚举组 A 状态 s 和选取数量 cnt_s
   • 从组 B 补充 k - cnt_s 个骨牌
   • 最大覆盖值 = f[s] + dp_g[s][k - cnt_s]
   • 答案 = 总和 - 最大覆盖值

3. 复杂度分析

• 时间复杂度：
  • 组 A DP：O(2^d · d) ≈ 2²¹ × 21 ≈ 4e6
  • 组 B 组合枚举：O(Σ_{t=0}^k C(|B|, t)) ≈ C(29,8) ≈ 4.3e6
  • 子集传递：O(2^d · d · k) ≈ 2²¹ × 21 × 9 ≈ 3.8e8
  • 总复杂度：O(3.8e8)（C++ 可接受）
• 空间复杂度：
  • 组 A DP：O(2^d) ≈ 2²¹ ≈ 2e6
  • 组 B DP：O(2^d · k) ≈ 2²¹ × 9 ≈ 1.8e7
  • 总空间：O(1.8e7)（约 72 MB）

---

代码实现

C++解法

cpp
复制
1#include <bits/stdc++.h>
2#define fi first
3#define se second
4#define INF INT_MAX
5#define cnt __builtin_popcount
6using namespace std;
7constexpr int N = 4e6 + 9, M = 50, W = 21;
8int n, k, tot, d, val[N], ans, sum;
9pair<int, int> dm[N << 1];
10
11// 二维坐标转一维索引
12int id(int x, int y) { return x * n + y; }
13
14// 获取骨牌覆盖值
15int getval(pair<int, int> x) { return val[x.fi] + val[x.se]; }
16
17// 检查两骨牌是否冲突（共享单元格）
18bool issim(pair<int, int> x, pair<int, int> y) {
19  return x.fi == y.fi || x.fi == y.se || x.se == y.fi || x.se == y.se;
20}
21
22// 安全加法（处理 INF 溢出）
23int iadd(int x, int y) { return x == INF || y == INF ? INF : x + y; }
24
25int f[1 << W];            // 组A状态DP数组
26int gval[1 << W][9];      // 组B状态DP数组
27int gstB[M];              // 组B骨牌与组A的冲突掩码
28
29int main() {
30  ios::sync_with_stdio(false), cin.tie(nullptr);
31  cin >> n >> k;
32  // 读入网格并计算总和
33  for (int i = 0; i < n; ++i)
34    for (int j = 0; j < n; ++j) {
35      cin >> val[id(i, j)];
36      sum += val[id(i, j)];
37      // 生成候选骨牌（下/右方向）
38      if (i) dm[tot++] = {id(i - 1, j), id(i, j)}; // 纵向骨牌
39      if (j) dm[tot++] = {id(i, j - 1), id(i, j)}; // 横向骨牌
40    }
41
42  // 贪心剪枝：保留值最大的50个骨牌
43  if (tot > M) {
44    nth_element(dm, dm + M, dm + tot, [](auto x, auto y) {
45      return getval(x) > getval(y);
46    });
47    tot = M;
48  }
49  d = min(tot >> 1, W); // 组A大小（不超过21）
50
51  // 初始化组A状态DP
52  for (int i = 0; i < d; ++i) {
53    f[1 << i] = getval(dm[i]); // 单骨牌状态
54    for (int j = 0; j < i; ++j)
55      if (issim(dm[i], dm[j])) 
56        f[(1 << i) | (1 << j)] = INF; // 标记冲突
57  }
58
59  // 组A状态转移（枚举子集）
60  for (int i = 0; i < d; ++i)
61    for (int s = 0; s < (1 << d); ++s)
62      if ((s >> i & 1) && cnt(s) <= k) 
63        f[s] = iadd(f[s], f[s ^ (1 << i)]); // 状态累加
64
65  // 初始化组B冲突掩码（默认不冲突）
66  for (int i = 0; i < tot - d; ++i)
67    gstB[i] = (1 << d) - 1;
68
69  // 预处理组B与组A的冲突关系
70  for (int i = 0; i < tot - d; ++i)
71    for (int j = 0; j < d; ++j)
72      if (issim(dm[i + d], dm[j])) 
73        gstB[i] &= ~(1 << j); // 标记冲突位
74
75  // 初始化组B状态DP
76  memset(gval, -0x3f, sizeof(gval)); // 初始化为负无穷
77  gval[(1 << d) - 1][0] = 0;         // 空集状态
78
79  // 枚举组B骨牌组合
80  for (int i = 0; i < tot - d; ++i) {
81    int w = getval(dm[i + d]); // 当前骨牌值
82    for (int s = (1 << d) - 1; s >= 0; --s) {
83      int allow = s & gstB[i]; // 当前允许的组A状态
84      for (int t = 0; t < k; ++t) {
85        if (gval[s][t] < -1e9) continue; // 无效状态
86        // 更新添加当前骨牌后的状态
87        if (gval[allow][t + 1] < gval[s][t] + w)
88          gval[allow][t + 1] = gval[s][t] + w;
89      }
90    }
91  }
92
93  // 组B子集传递（高位向低位）
94  for (int i = 0; i < d; ++i)
95    for (int s = 0; s < (1 << d); ++s)
96      for (int t = 0; t <= k; ++t)
97        if (s >> i & 1) // 若第i位为1，传递到子集
98          gval[s ^ (1 << i)][t] = max(gval[s ^ (1 << i)][t], gval[s][t]);
99
100  // 合并组A和组B结果
101  for (int s = 0; s < (1 << d); ++s) {
102    if (f[s] == INF) continue;         // 跳过无效状态
103    int cntA = cnt(s);
104    if (cntA > k) continue;            // 超过k个骨牌
105    int maxB = gval[s][k - cntA];      // 组B补充结果
106    if (maxB < -1e9) continue;         // 无效状态
107    ans = max(ans, f[s] + maxB);       // 更新最大覆盖值
108  }
109
110  cout << sum - ans << endl; // 输出最小可见和
111  return 0;
112}

代码解释：

1. 核心数据结构：

   • val[]：网格一维化存储
   • dm[]：候选骨牌（单元格对）
   • f[]：组A状态压缩DP数组
   • gval[][]：组B状态DP数组（二维：状态×骨牌数）

2. 关键逻辑：

   • 贪心剪枝（第38-43行）：nth_element部分排序保留前50大骨牌
   • 组A状态转移（第55-59行）：枚举子集累加合法状态
   • 组B状态更新（第83-91行）：类似背包DP，更新添加骨牌后的状态
   • 子集传递（第97-102行）：高位状态向低位传递最优值
   • 结果合并（第107-114行）：枚举组A状态，补充组B骨牌

3. 特殊处理：

   • 边界条件：k=0时直接输出总和（未显式处理，因DP包含空集）
   • 冲突检测：issim()函数检查两骨牌是否共享单元格
   • INF处理：iadd()防止整数溢出

---

Python3解法

python
复制
1import sys
2import heapq
3
4def main():
5    data = sys.stdin.read().split()
6    n = int(data[0])
7    k = int(data[1])
8    grid = []
9    total_sum = 0
10    index = 2
11    # 读入网格并计算总和
12    for i in range(n):
13        row = list(map(int, data[index:index+n]))
14        grid.append(row)
15        total_sum += sum(row)
16        index += n
17        
18    if k == 0:
19        print(total_sum)
20        return
21        
22    candidates = []
23    directions = [(0, 1), (1, 0)]  # 右/下两个方向
24    
25    # 生成候选骨牌
26    for i in range(n):
27        for j in range(n):
28            for dx, dy in directions:
29                ni, nj = i + dx, j + dy
30                if 0 <= ni < n and 0 <= nj < n:
31                    val = grid[i][j] + grid[ni][nj]
32                    candidates.append((val, (i, j), (ni, nj)))
33    
34    # 贪心剪枝：保留值最大的50个骨牌
35    if len(candidates) > 50:
36        candidates = heapq.nlargest(50, candidates, key=lambda x: x[0])
37    
38    dominoes = candidates
39    tot = len(dominoes)
40    d = min(tot // 2, 21)  # 组A大小上限21
41    groupA = dominoes[:d]  # 组A：前d个骨牌
42    groupB = dominoes[d:]   # 组B：剩余骨牌
43    lenB = len(groupB)
44    
45    # 获取骨牌覆盖的单元格
46    def get_cells(dom):
47        return {dom[1], dom[2]}
48
49    # 预处理组A内部冲突
50    conflictA = [0] * d
51    for i in range(d):
52        cells_i = get_cells(groupA[i])
53        for j in range(d):
54            if i == j: continue
55            cells_j = get_cells(groupA[j])
56            if cells_i & cells_j:  # 存在共享单元格
57                conflictA[i] |= (1 << j)  # 标记冲突位
58
59    # 预处理组B与组A的冲突
60    gstB = [(1 << d) - 1] * lenB
61    for i in range(lenB):
62        cells_i = get_cells(groupB[i])
63        for j in range(d):
64            cells_j = get_cells(groupA[j])
65            if cells_i & cells_j:
66                gstB[i] &= ~(1 << j)  # 清除冲突位
67
68    # 预处理组B内部冲突
69    conflictB = [0] * lenB
70    for i in range(lenB):
71        cells_i = get_cells(groupB[i])
72        for j in range(lenB):
73            if i == j: continue
74            cells_j = get_cells(groupB[j])
75            if cells_i & cells_j:
76                conflictB[i] |= (1 << j)  # 标记冲突位
77
78    # 组A状态DP：f[state]表示状态state的最大覆盖值
79    f = [-10**18] * (1 << d)
80    f[0] = 0  # 初始状态
81    for state in range(1 << d):
82        if f[state] < 0: continue
83        for i in range(d):
84            if state & (1 << i): continue     # 已选该骨牌
85            if state & conflictA[i]: continue  # 与已选骨牌冲突
86            new_state = state | (1 << i)
87            new_val = f[state] + groupA[i][0]  # 添加骨牌值
88            if new_val > f[new_state]:
89                f[new_state] = new_val
90
91    # 处理无组B骨牌的情况
92    if lenB == 0:
93        max_cover = max(f[s] for s in range(1<<d) 
94                    if bin(s).count('1') <= k and f[s] >= 0)
95        print(total_sum - max_cover)
96        return
97        
98    # 组B状态DP：dp_g[state][t]表示在组A状态state下选t个骨牌的最大值
99    dp_g = [[-10**18] * (k+1) for _ in range(1 << d)]
100    
101    # 枚举组B选取数量t
102    for t in range(0, min(lenB, k) + 1):
103        # 枚举所有t个骨牌的组合
104        from itertools import combinations
105        for combo in combinations(range(lenB), t):
106            maskT = 0
107            conflict_flag = False
108            # 检查组合内部冲突
109            for i in combo:
110                if maskT & conflictB[i]:  # 存在冲突
111                    conflict_flag = True
112                    break
113                maskT |= (1 << i)
114            if conflict_flag: continue
115            
116            total_val = 0
117            gsts = (1 << d) - 1
118            # 计算总覆盖值和组A冲突掩码
119            for i in combo:
120                total_val += groupB[i][0]
121                gsts &= gstB[i]  # 合并冲突掩码
122            
123            # 更新DP数组
124            if total_val > dp_g[gsts][t]:
125                dp_g[gsts][t] = total_val
126
127    # 子集传递：高位状态向低位传递最优值
128    for t in range(0, k+1):
129        for i in range(d):
130            for state in range(1 << d):
131                if state & (1 << i):
132                    prev = state ^ (1 << i)
133                    if dp_g[prev][t] < dp_g[state][t]:
134                        dp_g[prev][t] = dp_g[state][t]
135
136    # 合并组A和组B结果
137    max_cover = 0
138    for state in range(1 << d):
139        cntA = bin(state).count('1')
140        if cntA > k or f[state] < 0: continue
141        rem = k - cntA
142        bestB = max(dp_g[state][:rem+1])  # 组B补充rem个骨牌
143        if bestB < 0: continue
144        max_cover = max(max_cover, f[state] + bestB)
145
146    print(total_sum - max_cover)
147
148if __name__ == "__main__":
149    main()

代码解释：

1. 与C++实现差异：

   • 组合枚举：直接使用itertools.combinations枚举组B骨牌组合（C++通过位运算优化）
   • 冲突检测：显式检查组合内骨牌冲突（C++通过预计算掩码）
   • DP数组初始化：Python初始化为负无穷（-10**18），C++用-0x3f

2. Python特性应用：

   • 堆选TOP-K：heapq.nlargest高效选取最大50个骨牌
   • 集合运算：get_cells()返回单元格集合，用&检测交集
   • 组合生成：itertools.combinations简化组合枚举

3. 关键逻辑：

   • 组A DP（第60-70行）：状态转移时跳过冲突骨牌
   • 组B组合处理（第89-108行）：枚举有效组合并更新DP
   • 子集传递（第112-118行）：通过位操作传递最优解
   • 结果合并（第123-130行）：取组A状态对应组B最优补充值

---

复杂度对比

场景建议：

• 竞赛场景：首选C++实现，尤其当 n 较大时
• 快速原型：选用Python实现，代码更易理解和修改
• k值较大时：若 k>8，需调整候选骨牌数量（当前50足够）