T9:Gold King精品工程

解题思路（2×n 用 1×2 小板铺满）

这是经典的 2×n 骨牌覆盖 问题。每块地板是 1×2，可以横着放（占一行两列）或竖着放（占两行一列）。

设 dp[i] 表示铺满 2×i 大青板的方案数。

考虑最后一列/最后两列的摆放方式：

1. 最后一块竖放

竖着放一块 1×2（实际覆盖两行一列），就把问题变成铺满 2×(i-1)：

• 贡献 dp[i-1]

2. 最后两块横放（上下各一块）

如果最后一列不是竖放，那为了铺满最后两列，只能在上下两行各横放一块，覆盖 2×2 的区域：

• 贡献 dp[i-2]

因此得到递推：

• dp[i] = dp[i-1] + dp[i-2]

初始条件：

• dp[1] = 1（2×1 只能竖放 1 种）
• dp[2] = 2（2×2：两块竖放，或两块横放）

答案输出 dp[n]。

（这就是斐波那契型递推，n ≤ 60 用 long long 足够。）

---

C++ 代码

#include <iostream>
using namespace std;

long long dp[65];

int main() {
    int n;
    cin >> n;

    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    cout << dp[n] << endl;
    return 0;
}