首页 > ACM题库 > HDU-杭电 > hdu 2606 Renovation Problem-递推-[解题报告]C++
2014
02-12

hdu 2606 Renovation Problem-递推-[解题报告]C++

Renovation Problem

问题描述 :

The New Year’s Day is comming ! Every family want to make theiir house looks more beautiful , so does Teddy’s . To make his own house looks different from other’s , he went to the shop to buy four kinds of tiles . each kind of tiles has different size : 1*1 , 2*2 , 3*3 and 4 * 4, respectively .

The problem is , how many ways there are to tile his floor which has a area of 4*N using these four kinds of tiles ? You can assume that the number of each kind of tiles is enough.

输入:

The first line contain a T. followed by T lines ,each line contain a integer N.(1<=N <=100).

输出:

The first line contain a T. followed by T lines ,each line contain a integer N.(1<=N <=100).

样例输入:

2
1
2

样例输出:

1
5

/*
分析:
    简单递推。
    注意对于2*n(n>=3),是可以由2*2的格子交错组合
而成的,eg:
n=3:
    ..#
    ..#
    #..
    #..
n=4:
    ….
    ….
    #..#
    #..#

                                     2013-01-23
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
int ans[111];
void init()
{
	int i,l;
	ans[0]=1;
	ans[1]=1;
	ans[2]=ans[1]+4*ans[0];
	ans[3]=ans[2]+4*ans[1]+2*ans[0]+2*ans[0];
	for(i=4;i<=100;i++)
	{
		ans[i]=(ans[i-1]+4*ans[i-2]+2*ans[i-3]+ans[i-4])%19890907;
		for(l=3;l<=i;l++)	ans[i]=(ans[i]+2*ans[i-l])%19890907;
	}
	return ;
}
int main()
{
	init();
	int T,n;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		printf("%d\n",ans[n]);
	}
	return 0;
}

解题转自:http://blog.csdn.net/ice_crazy/article/details/8533794