DP练习记录

[HNOI2004] 敲砖头

——这题暑假时做过，但是全忘了QAQ。

最初的思路和这篇题解一开始想到的思路差不多，就是设 $f[i][j][k]$ 表示到第 $i$ 行，第 $j$ 列，敲掉 $k$ 个砖头后的最大得分。但是感觉推不出转移方程式，原因在于我觉得$f[i][j][k]$ 需要从 $f[i-1][j][x]$ , $f[i-1][j-1][y]$ 还有其他的许多地方推导出来（还需要用到其他地方是因为答案是由多个倒三角拼成，你总不能就一个倒三角）这样的话存在不符合无后效性的情况。因为设的一个状态由另外哪些状态推导出来决定了你的DP过程中for循环的循环方式，但是对于上面这种情况很难找到一种时间复杂度正确的循环方式。不过也感谢上面这篇题解提供了一种通用解决方法（只不过对于这道题来说时间复杂度过大），也就是使用二进制记忆上一行选择了哪些砖块敲掉。

考虑只在一个倒三角的轮廓线（即上图紫色线）上进行DP的转移。由于在一个倒三角形的轮廓上，对于 $(i,j)$ ，只会从 $(i-1,j)$ 和 $(i+1,j-1)$ 推导，所以问题也就解决了。