「NOI2013」书法家 题解 一、题目核心分析

1. 题目本质 本题是带图形约束的最大权值和问题，核心目标是在 (n \times m) 矩阵中选择三个满足特定几何约束的图形（N、O、I），使得三者覆盖的方格幸运值之和最大。关键特点： 图形约束严格：N、O、I 的结构、位置关系（间隔至少 1 列）均有明确要求； 规模限制：(n \le 150)，(m \le 500)，需设计 (O(n^2 m)) 级别的算法； 权值可负：需考虑 “必须选满三个图形” 的约束（即使权值为负，也不能跳过）。
2. 核心观察 位置顺序固定：N 在最左，O 在中间（与 N 间隔≥1 列），I 在最右（与 O 间隔≥1 列）； 图形可拆解为矩形组合：所有图形均由矩形（或矩形挖空）构成，可用二维前缀和快速计算区域权值和； 分阶段求解：可按列划分区域（左段 N、中段 O、右段 I），用 DP 分别记录每段的最优状态，最后合并三段结果。 二、预处理：二维前缀和（快速计算矩形权值和） 由于频繁需要计算矩形区域的幸运值和，先预处理二维前缀和数组，将单次矩形和查询优化到 (O(1))。
3. 坐标映射与前缀和定义 题目中坐标定义：左下角为 ((1,1))，右上角为 ((m,n))，第 (i+1) 行第 (j) 列对应格子 ((j, n-i+1))。为方便计算，将输入矩阵转换为 “常规坐标”（行号从下到上为 (1 \sim n)，列号从左到右为 (1 \sim m)），记为 (grid[x][y])（(x)：列，(y)：行）。 二维前缀和数组 (pre[x][y]) 定义为： (pre[x][y] = \sum_{i=1}^x \sum_{j=1}^y grid[i][j])
4. 前缀和计算与矩形和查询 预处理前缀和： (pre[x][y] = grid[x][y] + pre[x-1][y] + pre[x][y-1] - pre[x-1][y-1]) 矩形和查询：左下角 ((a,b))、右上角 ((c,d)) 的区域和为： (sum = pre[c][d] - pre[a-1][d] - pre[c][b-1] + pre[a-1][b-1]) 三、分阶段 DP 设计 整体思路：用三个 DP 数组分别记录 “N 的最优状态”“N+O 的最优状态”“N+O+I 的最优状态”，最后取全局最大值。 阶段 1：预处理 N 的最优状态（DP_N [x]）
5. N 的图形特征拆解 N 由 (K \ge 3) 个连续列的矩形组成（列从 (L_1) 到 (R_K)），核心约束可简化为： 列连续：第 (i) 个矩形占第 (x) 列（(x) 从左到右递增）； 上下边界变化：左起第 1 列（矩形 1）有固定上下界 ((b1, t1))；第 2 列（矩形 2）下界 (b2 > b1)、上界 (t2 = t1)；中间列（3~K-2）下界非递增、上界≤前一列上界且≥前一列下界 - 1；最后两列（K-1、K）下界固定，上界递增。
6. N 的 DP 状态设计 定义 (DP_N[x][b][t])：表示 N 的右边界在第 (x) 列，当前列矩形的下界为 (b)、上界为 (t) 时，N 的最大权值和。 状态转移（按列从左到右递推）： 初始列（(x = l)，N 的左起点）：需满足 (K \ge 3)，即至少占 3 列，初始列的 ((b,t)) 为矩形 1 的边界，权值为该列矩形的和； 中间列（(x > l)）：根据 N 的约束，当前列的 ((b,t)) 需满足与前一列 ((b',t')) 的关系（如 (b \le b')、(t' -1 \le t \le t') 等），权值为前一列 DP 值 + 当前列矩形和。
7. 优化：压缩状态维度 由于 (n \le 150)，(x \le 500)，直接用 (DP_N[x][b][t]) 会导致空间复杂度 (O(m n^2) = 500 \times 150^2 = 11,250,000)，可接受。但需进一步优化转移效率： 预处理每列所有可能 ((b,t)) 的矩形和（用前缀和快速计算）； 转移时按约束筛选合法的前一列 ((b',t'))，取最大值。 最终，(DP_N) 的最优值为所有满足 “N 占列数≥3” 的 (DP_N[x][b][t])。为后续 O 的计算，我们还需记录 (DP_N_{max}[x])：表示 N 的右边界≤(x) 列时的最大权值和（即截至第 (x) 列，N 的最优解）。 阶段 2：预处理 O 的最优状态（DP_O [x1][x2]）
8. O 的图形特征拆解 O 是 “大矩形挖小矩形”，核心约束： 大矩形：左下角 ((u,v))，长 (W)（列数 (x2 - x1 + 1)），宽 (H)（行数 (t - b + 1)），满足 (W \ge 3)，(H \ge 3)； 小矩形：左下角 ((u+1, v+1))，长 (W-2)，宽 (H-2)（挖去的区域）； 位置：O 的左边界 (u > R_K + 1)（与 N 间隔至少 1 列）。
9. O 的权值计算 O 的权值 = 大矩形和 - 小矩形和（用前缀和快速计算）。
10. DP 状态设计 定义 (DP_O[x1][x2])：表示 O 占据第 (x1 \sim x2) 列（(x2 - x1 + 1 \ge 3)）时，O 的最大权值和。 计算方式： 枚举所有可能的 (x1, x2)（(x2 \ge x1 + 2)）； 枚举 O 的大矩形上下边界 ((b,t))（(t - b + 1 \ge 3)）； 计算大矩形和 - 小矩形和，取最大值作为 (DP_O[x1][x2])。 为后续合并 N 和 O，定义 (DP_NO_{max}[x2])：表示 N 的右边界≤(x1 - 2)（与 O 间隔≥1 列）且 O 的右边界为 (x2) 时，(N + O) 的最大权值和（即 (DP_N_{max}[x1-2] + DP_O[x1][x2])）。 阶段 3：预处理 I 的最优状态（DP_I [x]）
11. I 的图形特征拆解 I 由 3 个上下排列的矩形组成，核心约束： 下矩形（1 号）和上矩形（3 号）：列范围相同（(P1 \sim G1)），行范围分别为 ((Q1, Q1)) 和 ((Q3, Q3))（单行矩形）； 中矩形（2 号）：列范围 (P2 \sim G2)（(P1 2 \le G2 < G1)），行范围 ((Q2, H2))（(Q2 = Q1 + 1)，(H2 + 1 = Q3)）； 位置：I 的左边界 (P1 > u + W)（与 O 间隔≥1 列）。
12. I 的权值计算 I 的权值 = 下矩形和 + 中矩形和 + 上矩形和（均用前缀和计算）。
13. DP 状态设计 定义 (DP_I[x])：表示 I 的左边界≥(x) 列时，I 的最大权值和。 计算方式： 枚举 I 的列范围（(P1 \sim G1)，(P2 \sim G2)），满足 (G1 - P1 + 1 \ge 3)（因 $P1 2 ； 枚举 I 的行范围（(Q1, Q2, Q3)），满足 (Q3 - Q1 + 1 \ge 3)； 计算三个矩形的权值和，取最大值作为 (DP_I[x])（(x) 为 I 的左边界）。 阶段 4：合并三者的最大权值和 最终答案为所有满足 “位置约束” 的 (N + O + I) 权值和的最大值，即： (max_ans = \max_{x1, x2, x3} { DP_N_{max}[x1-2] + DP_O[x1][x2] + DP_I[x2+2] }) 其中： (x1)：O 的左边界，需满足 (x1 \ge x_N + 2)（N 与 O 间隔≥1 列）； (x2)：O 的右边界，需满足 (x2 \ge x1 + 2)（O 占列≥3）； (x3)：I 的左边界，需满足 (x3 \ge x2 + 2)（O 与 I 间隔≥1 列）。 四、关键优化策略
14. 前缀和优化矩形和计算 所有矩形和均通过二维前缀和 (O(1)) 计算，避免重复遍历矩阵，是算法高效的基础。
15. 状态压缩与转移剪枝 对于 N 的 DP 转移，按图形约束筛选合法状态（如 (b \le b')、(t \le t') 等），减少无效转移； 对于 O 的枚举，仅需枚举列范围 (x1 \sim x2) 和上下边界 ((b,t))，无需额外状态转移； 对于 I 的计算，预处理所有合法 I 的最大权值和，按左边界存储，方便后续查询。
16. 边界情况处理 权值为负：即使所有方格权值为负，也需选满三个图形（如样例 2，输出为 - 20）； 图形边界不越界：所有图形的列范围需在 (1 \sim m)，行范围需在 (1 \sim n)； 间隔约束：N 与 O、O 与 I 均需间隔至少 1 列，避免重叠。 五、完整解题步骤 输入处理与坐标映射：将输入矩阵转换为 “列左到右、行下到上” 的常规坐标，计算二维前缀和； 预处理 DP_N：递推计算所有 N 的合法状态，得到 (DP_N_{max}[x])； 预处理 DP_O：枚举所有 O 的合法列范围和边界，得到 (DP_O[x1][x2]) 和 (DP_NO_{max}[x2])； 预处理 DP_I：枚举所有 I 的合法结构，得到 (DP_I[x])； 合并三者结果：枚举所有满足位置约束的组合，计算 (N+O+I) 的最大权值和。 六、代码框架（伪代码）

1. 预处理前缀和

def preprocess(): n, m = map(int, input().split()) grid = [[0](n+2) for _ in range(m+2)] # grid[x][y]: x列y行 for i in range(n): row = list(map(int, input().split())) for j in range(m): x = j + 1 y = n - i # 映射到下到上的行号 grid[x][y] = row[j] # 计算二维前缀和 pre = [[0](n+2) for _ in range(m+2)] for x in range(1, m+1): for y in range(1, n+1): pre[x][y] = grid[x][y] + pre[x-1][y] + pre[x][y-1] - pre[x-1][y-1] return n, m, grid, pre

2. 计算 DP_N 和 DP_N_max

def compute_DP_N(n, m, pre): INF = -1e18 DP_N = [[[INF](n+2) for _ in range(n+2)] for __ in range(m+2)] DP_N_max = [INF](m+2) # 枚举 N 的左边界 l 和右边界 r（r >= l+2，至少3列） for l in range(1, m-1): for r in range(l+2, m+1): # 初始化 l 列的状态（矩形1） for b1 in range(1, n+1): for t1 in range(b1, n+1): sum1 = get_rect_sum(pre, l, b1, l, t1) DP_N[l][b1][t1] = sum1 # 递推 l+1 到 r 列 for x in range(l+1, r+1): for b in range(1, n+1): for t in range(b, n+1): sum_x = get_rect_sum(pre, x, b, x, t) # 枚举前一列 x-1 的合法状态 (b_prev, t_prev) max_prev = INF for b_prev in range(b, n+1): # N 的约束：b for t_prev in range(t, min(n, t+1)+1): # N 的约束：t_prev-1 t if DP_N[x-1][b_prev][t_prev] != INF: max_prev = max(max_prev, DP_N[x-1][b_prev][t_prev]) if max_prev != INF: DP_N[x][b][t] = max_prev + sum_x # 更新 DP_N_max[r]：r 列是 N 的右边界时的最大值 current_max = INF for b in range(1, n+1): for t in range(b, n+1): current_max = max(current_max, DP_N[r][b][t]) DP_N_max[r] = max(DP_N_max[r], current_max) # 累计 DP_N_max（截至 x 列的最大 N 权值） for x in range(1, m+1): DP_N_max[x] = max(DP_N_max[x], DP_N_max[x-1]) return DP_N_max

3. 计算 DP_O 和 DP_NO_max

def compute_DP_O(n, m, pre): INF = -1e18 DP_O = [[INF](m+2) for _ in range(m+2)] # DP_O[x1][x2]: O 占 x1~x2 列 DP_NO_max = [INF](m+2) # 枚举 O 的列范围 x1~x2（x2 >= x1+2，宽>=3） for x1 in range(1, m-1): for x2 in range(x1+2, m+1): W = x2 - x1 + 1 if W 3: continue # 枚举 O 的大矩形上下边界 b~t（高>=3） max_o = INF for b in range(1, n-1): for t in range(b+2, n+1): H = t - b + 1 if H < 3: continue # 大矩形和：x1~x2 列，b~t 行 sum_big = get_rect_sum(pre, x1, b, x2, t) # 小矩形和：x1+1~x2-1 列，b+1~t-1 行 sum_small = get_rect_sum(pre, x1+