描述
有一个大小是 2 x n 的网格，现在需要用 2 种规格的骨牌铺满，骨牌规格分别是 2 x 1 和 2 x 2，请计算一共有多少种铺设的方法。
输入
输入的第一行包含一个正整数 T（T <= 20），表示一共有 T 组数据。
接着是 T 行数据，每行包含一个正整数 N (N <= 30)，表示网格的大小是 2 行 N 列。
输出
对于每组测试数据，请输出铺放方案的总数，每组数据输出一行。
输入样例 1
3 2 8 12
输出样例 1
3 171 2731
这个问题可以通过动态规划来解决。我们需要计算在 \(2 \times n\) 的网格中用 \(2 \times 1\) 和 \(2 \times 2\) 的骨牌铺满的方案总数。
### 分析
1. **Base Cases**:
- 当 \(n = 1\) 时，只有一种铺法：竖着放一个 \(2 \times 1\) 的骨牌。
- 当 \(n = 2\) 时，有三种铺法：两个骨牌都竖着放，或者两个骨牌都横着放，或者放一个 \(2 \times 2\) 的骨牌。
2. **Recursive Relation**:
- 对于 \(n \geq 3\)，我们可以考虑最后一块骨牌的放法：
- 如果最后一块骨牌是竖着放的，那么剩下的部分是 \(2 \times (n-1)\) 的网格。
- 如果最后两块骨牌是横着放的，那么剩下的部分是 \(2 \times (n-2)\) 的网格。
- 如果最后一块骨牌是 \(2 \times 2\) 的骨牌，那么剩下的部分也是 \(2 \times (n-2)\) 的网格。
- 因此，递推关系为：\(dp[n] = dp[n-1] + 2 \times dp[n-2]\)。
### 代码实现
```c
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
long long dp(int n) {
if (n == 1) return 1;
if (n == 2) return 3;
long long dp[31];
dp[1] = 1;
dp[2] = 3;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + 2 * dp[i - 2];
}
return dp[n];
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
long long result = dp(n);
printf("%lld\n", result);
}
return 0;
}
```
### 解释
1. **Base Cases**:
- `dp[1] = 1`：只有一种铺法。
- `dp[2] = 3`：有三种铺法。
2. **Dynamic Programming Array**:
- `dp[i]` 表示 \(2 \times i\) 的网格的铺法总数。
- 递推关系：`dp[i] = dp[i-1] + 2 * dp[i-2]`。
3. **Main Function**:
- 读取输入的整数 `T`，表示测试数据的组数。
- 对于每组测试数据，读取整数 `n`。
- 调用 `dp` 函数计算铺法总数。
- 输出结果。
### 示例
对于输入：
```
3
2
8
12
```
输出将是：
```
3
171
2731
```
### 总结
- 这个问题可以通过动态规划来解决，递推关系为 `dp[n] = dp[n-1] + 2 * dp[n-2]`。
- 代码实现中，我们使用了一个数组来存储中间结果，以避免重复计算。
- 最终输出每组测试数据的铺法总数。