ABC311-F

2023-08-29 23:54 作者:_Sunlight9 0人读过 | 我要投稿

一道很好的DP题。

我们发现一个符合要求的图案，当某一点是黑色时，从这个点开始沿对角线方向向下一定都得是黑色。

所以我们设 $f%5Bj%5D%5Bi%5D$ 表示前 $j$ 列，出现黑色点的第一行为 $i$ 时的方案数，特别地，当 $i%3D%3Dn$ 时，表示这一列没有黑色点(坐标从 $0$ 开始)。

则 $f%5Bj%5D%5Bi%5D%20%3D%20%5Csum_%7Bk%3Dmax(0%2Ci-1)%7D%5Enf%5Bj-1%5D%5Bk%5D$ ,当 $a%5Bi%5D%5Bj%5D%20%3D%3D%20%20%5C%20'%5C%23%20%5C%20%20'$ 时结束转移。

最终答案为 $%5Csum_%7Bi%3D0%7D%5Enf%5Bm%5D%5Bi%5D$ .

可以用滚动数组优化空间。

二维数组版本

滚动数组版本

标签：

ABC311-F的评论 (共条)