题解：AT_ndpc2026_a ポリオミノ

违规用户名1377536 · 2026-05-12 23:21:32 · 题解

AT_ndpc2026_a ポリオミノ Solution

安利一下我的博客。

DP 水题一枚。DP 三要素走起！

1. 状态定义

定义 f_i 为填充 2 行 i 列的方案数。

2. 转移方程

若竖着填充一块 1\times2 的多连块，则 f_{i}\to f_{i+1}；
若横着填充一块 1\times2 的多连块，则 f_i \to f_{i+2}；
若填充一块 L 形的多连块，必须相应的再添加一块 L 形的多连块。
由于左边 L 形的多连块有两种放法（必须保证“开口”朝右），所以 f_i\times2 \to f_{i+3k}（k 为正整数）。

3. 状态初始化

### 代码 :::success[Code]{open} ```cpp cin >> n; f[0] = 1; for (int i = 0; i <= n; i++) { f[i+1] += f[i]; f[i+2] += f[i]; for (int j = i+3; j <= n; j++) f[j] += f[i]*2; } cout << f[n]; ``` :::