P1437 [HNOI2004] 敲砖块——超酷的dp

· · 个人记录

思路

初见发现可能要状压，但是这个数据量是不太好状压的

看有按列枚举的，我没看懂

但是可以观察到这时选中敲掉的砖块有一个折线的轮廓（断掉不敲的部分可以视为跑到了第 0 行）

于是可以把这个折线跑的每一步看作一个阶段，求解从左下角到右下角的折线围出砖块的最大权值和

当然这样直接状态不太好划分，所以还是三维状态

对于非 $0$ 行，有两个决策，从上面来和从下面来 $$dp_{i,j,k}=\max(dp_{i+1.j-1,k-i}+\sum_{l=1}^{i}val_{l,j},dp_{i,j-1,k-1}+val_{i,j})$$ 加个前缀和维护即可 对于 $0$ 行，也有两个决策，从其他 $0$ 行来和从下面来 $$dp_{i,j,k}=\max(dp_{i+1,j-1,k},dp_{i,j-1,k})$$ 最后代码实现的时候，要注意如果当前都拆不到，就不要加权值了