悼念512汶川大地震遇难同胞——重建希望小学 HDU - 2190

下面是512汶川大地震部分受灾学校伤亡情况（惨痛！！） 

1、 四川省都江堰市 聚源中学 
伤亡情况：遇难学生人数（含失踪）320 
详细说明： 一栋教学楼被震垮，该楼18个班420多名学生被埋，截至目前仅有不到100名获救。 
2、 四川省绵阳市 北川县北川中学 
伤亡情况：遇难学生人数（含失踪）1200多人 
详细说明：学校教室损毁情况严重，六至七层高的主教学楼已经垮塌得只有一人多高，其他两个教学楼和宿舍也有不同程度垮塌 
3、四川省绵阳市 北川县曲山小学（绵阳市示范小学） 
伤亡情况：遇难学生人数（含失踪）698人 
详细说明：学校位于北川县郊一公里处的任家坪镇，在校师生人数 1003人，地震使学校一座五层教学楼的整体倒塌，只剩下了一层 
4、四川省绵阳市 北川县曲山幼儿园 
伤亡情况：在校师生人数500多，仅生还20余人 
详细说明：学校位于绵阳市北川县曲山镇危家巷，曲山幼儿园及学前班500多名学生被滑坡气浪推移20多米，教学大楼像竹编一样倒下，整体向外挪出五十公分仅凭肉眼根本无法作出判断这是四层楼…… 
5、四川省绵阳市 北川县茅坝初中 
伤亡情况：在校师生人数240多，仅生还20余人 
详细说明：教室被泥石流掩埋，学校只剩一根歪歪斜斜的旗杆和一面鲜艳的五星红旗…… 
….. 


为什么会有这么多的学校伤亡惨重？也许有很多值得我们调查的东西。但对于我们来说，当前最紧迫的任务是重建学校，以便让幸存的学生早日走进课堂。 
这不，一所由社会各界捐款修建的希望小学马上就要竣工了！学校教室的长度为n米，宽度为3米，现在我们有2种地砖，规格分别是1米×1米，2米×2米，如果要为该教室铺设地砖，请问有几种铺设方式呢？ 

Input输入数据首先包含一个正整数C，表示包含C组测试用例，然后是C行数据，每行包含一个正整数n(1<=n<=30)，表示教室的长度。Output对于每组测试数据，请输出铺设地砖的方案数目，每个输出占一行。Sample Input

2
2
3

Sample Output

3
5

题意分析：学校教室的长度为n米，宽度为3米，现在我们有2种地砖，规格分别是1米×1米，2米×2米，铺设地板，有多少种方案，头一看，有点无从下手，后来发现是递推，说白了，也就是找规律（真不知道弄个这么高大上的名词干啥，难道只是为了让外行人听不懂）。

当n=1时：只能全部铺1*1的，有一种方案；

当n=2时：可以铺一个2*2加两个1*1，或者全部铺设1*1，有三种方案；

当n=3时：可以铺一个2*2加两个1*1，3*3的方块四个角铺一个2*2，其他用1*1填充，或者全部用1*1，有4+1=5种方案；

当n=4时：自己画一画就明白了，一共有11种方案，这里我就不在推理了；

现在总结一下:

长度为i，就是在（i-1）长度基础上新增了1，

1.可以让这新增的1*3区域铺三块1*1的砖，而前面部分就是a[i-1]种排法。

2.也可以考虑新增的1*3区域跟前一列用2*2的砖一块铺，由于宽度固定为3，那么最后这两列(2*3的区域)可以有两种排法(2*2的砖在上或在下)，而它们左边的排法是a[i-2]种，因此乘2。

因此得递推公式：a[i] = a[i-1] + 2*a[i-2].

代码送上：

#include<stdio.h>
int main()
{
	int a[35],t,n;
	a[1]=1,a[2]=3,a[3]=5;
	for(int i=4;i<35;i++)
	{
		a[i]=2*a[i-2]+a[i-1];
	}
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n);
		printf("%d\n",a[n]);
	}
	return 0;
}