题解：P2228 [HNOI2001] 洋洋吃蛋糕

· · 题解

题目传送门

问题核心约束

被选中的矩形需满足:

1.不重叠（行、列范围无交集）；

2.不相邻（行、列范围不连续，即中间至少隔一行或一列）。

状态定义

设 dp[i][mask] 表示：

#### 处理完前 i 行后，第 i 行的列占用状态为 mask 时的最大好吃度总和。

i：当前处理到的行（范围 0~n，i=0 表示未处理任何行，i=n 表示处理完所有行）。

mask：用m 位二进制数表示的列占用状态（mask 的第 j 位为 1 表示第 j 列被第 i 行的某个矩形占用）。

状态转移分析

从 dp[i][mask_prev] 转移到下一个状态时，有两种选择：

1.第 i 行不选任何矩形；

2.第 i 行选一个合法矩形。 情况 1：第 i 行不选任何矩形 此时，第 i 行无列占用（mask_curr = 0），且不会影响后续行的列选择（因为无占用，自然不冲突）。

转移方程：

dp[i+1][0] = max(dp[i+1][0], dp[i][mask_prev])
//从第 i 行的状态 mask_prev 转移到第 i+1 行，且第 i+1 行无任何占用，最大和保持不变。

情况 2：第 i 行选一个合法矩形

设选中的矩形满足：

1.行范围：[x1, x2]（x1 = i，即从当前行i开始）；

2.列范围：[y1, y2]，对应的列掩码为 mask_curr（y1~y2 对应的位为1）；

3.矩形的好吃度和为 val（val > 0，否则不选）。

需满足约束：

列不重叠：mask_prev & mask_curr == 0（前一行的列占用与当前矩形的列占用无交集）；

列不相邻：(mask_prev << 1) & mask_curr == 0 且 (mask_prev >> 1) & mask_curr == 0（前一行的列与当前矩形的列不左右相邻）。

转移方程：

dp[x2 + 1][mask_curr] = max(dp[x2 + 1][mask_curr], dp[i][mask_prev] + val)
//从第 i 行的状态 mask_prev 转移到第 x2 + 1 行（矩形结束后的下一行），状态更新为 mask_curr，最大和增加当前矩形的 val。

初始化与最终答案

初始化：dp[0][0] = 0（未处理任何行时，无占用，和为 0），其余状态初始化为-∞（表示不可达）。

最终答案：处理完所有行后，所有可能状态的最大值，即 max(dp[n][mask])（mask 为任意m 位二进制数）。

本人不才，点个赞再走呗