一道DP题；
一共有三种砖，1*2,2*1,2*2，然后要你铺满整个n*2的地板，求不重复的铺法数；
方法：
首先计算了不考虑对称的情况，然后计算只考虑对称的情况；
所以结果就是（不考虑对称数+只考虑对称数）/2；
递推关系：
dp[i] 表示左右各伸展 i 的对称情况。
dp[i+1] += dp[i] //两边补上 1 x 2
dp[i+2] += dp[i]*2//两边补上 2x1 跟 2x2 兩种。
然后只考虑对称的情况下有两种情况：
n==奇数：
中间有个1*2；
n==偶数；
中间有两个2*1；
或者两个2*1或者一个2*2；
代码：
#include<stdio.h>
#include<cstring>
using namespace std;
int dp1[],dp[]; int main()
{
int t;
int i, j, k, n;
dp1[] = ;
for(i = ; i < ; i++)
{
dp1[i+] += dp1[i]*;
dp1[i+] += dp1[i];
}
scanf("%d", &t);
while(t--)
{
memset(dp,,sizeof dp);
scanf("%d", &n);
if(n&)
{
dp[] = ;
dp[] = ;
for(i = ; i <= n/; i++)
{
dp[i+] += dp[i];
dp[i+] += dp[i]*;
}
printf("%d\n", (dp1[n]+dp[(n-)/])/);
}
else
{
dp[] = ;
dp[] = ;
for(i = ; i <= n/; i++)
{
dp[i+] += dp[i];
dp[i+] += dp[i]*;
}
printf("%d\n", (dp1[n]+dp[n/])/);
}
}
return ;
}