[luogu P1990] 覆盖墙壁

题目描述

点击此处题目描述

解题过程

递推

思路

本蒟蒻弱弱地看了题解才知道思路

$f[i]$ 表示铺满前 $i$ 列墙壁的方案数

如果最后以这种状态结尾，方案数是 $f[i?1]$

如果以这种状态结尾，方案数就是 $f[i?2]$

如果放 L 形，因为 L 形可以翻转，所以方案数要乘 2 ，放两个 L 形结尾，方案数就是 $f[i?3]$
放两个 L 形 和 一个 竖着的 结尾，方案数就是 $f[i?4]$
……
方案数一直到 $f[0]$
最后方案为 $2?(f[i?3]+f[i?4]+\dots +f[0])$

因此$f_i=2?{\sum }_{k=0}^{i?3}{f}_k+f_{i?1}+f_{i?2}={\sum }_{k=0}^{i?3}{f}_k+{\sum }_{k=0}^{i?1}{f}_k$

前缀和优化