AT_ndpc2026_a ポリオミノ 题解

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

1. 状态定义

定义fif_ifi​为填充222行iii列的方案数。

2. 转移方程

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

3. 状态初始化

222行000列的网格只有一种摆法，那就是不摆。所以f0=1f_0=1f0​=1。

代码

cin>>n;f[0]=1;for(inti=0;i<=n;i++){f[i+1]+=f[i];f[i+2]+=f[i];for(intj=i+3;j<=n;j++)f[j]+=f[i]*2;}cout<<f[n];