题解：P1437 [HNOI2004] 敲砖块

OMG_NOIP · 2024-04-09 09:35:27 · 个人记录

更大更清晰的图片

前置芝士

动态规划的无后效性

正文

原题面

分析：每一块选取的条件是其上方的两个数都要选。

尝试：

每个数从上往下取，每个数是否能取只和它上面两个数取没取有关。

设 dp_{i,j,k} 为第 (i,j) 个位置选了 k 个数字的最大值。

结果：

发现推不出状态转移方程，因为这样做不符合动态规划的无后效性。

具体哪里不符合动态规划的无后效性？

举例：

如下图的一组样例：

白色方框就是题目中的砖块。

蓝色的部分是我们现在选择的。

需要敲掉的数量就是蓝色砖块的数量，获得的价值就是所有蓝色砖块的价值和。

但如果之前已经选了下图的粉色部分

那么需要敲掉的数量就要减去重合的部分（即下图的紫色部分），获得的价值也要剪掉重合的部分。

因为同一块砖不用敲两次，价值也不能贡献两次。

这个例子说明当前选的砖块不只和它上方的两个砖块有关，还和其他的砖块有关，所以不满足动态规划的无后效性。

知道了为什么不能这样做，那要怎么办呢？

再次分析题目发现：这道题最终解选中的砖块可以描述成若干个三角形相互连接或重叠：

举例：

下图最终解选中的砖块就是三个三角形相互连接或重叠组成的。

我们将最终解的选中的方框的每列最下层点用线画出（图中的红线）试试：

我们发现这条红线有两个性质：

1. 如果从左向右观察，红线上的点只能从其左上方行或左下方行连过来的。

2. 红线上点其所有右上方点一定全部被选中。

   举例第二条性质，如图：

如果你选了上图中红色的点，那么蓝色的点一定全部被选中。紫色的点是之前选的。

那么就把原问题转化为沟画出重叠三角形的廓折线（图中的红线），找到一条合法的路径，使得围在轮廓线内的数字代价和最大。

验证：因为每个砖块只和其左上方和左下方的砖块有关，所以这个做法符合动态规划的无后效性。

具体实现

为了方面处理，先把上图居左对齐：

预处理 got_{i,j} 为选第 (i,j) 个砖块需要选的所有砖块的价值和。拿上图举例，如果你选的点是上图中红色的砖块，那么 got_{i,j} 就是 \text{红色砖块的价值+所有蓝色砖块的价值和}。

选第 (i,j) 个点需要敲掉的砖块数量就是 i\text{（行数）}。拿上图举例，如果你选的点是上图中红色的砖块，那就要敲掉红色砖块和所有蓝色砖块（紫色的是之前已经被敲掉了）。