首页 > 代码库 > HDU 2501 [Tiling_easy version] 递推

HDU 2501 [Tiling_easy version] 递推

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2501

题目大意:有2*N个格子,有2种牌(2*1的和2*2的),问有多少种铺满的方式。

关键思想:画图联想。找到递推式。

N为奇数时,dp[n]=2*dp[N-1]-1.

N为偶数时,dp[n]=4*dp[N-2]-1.

代码如下:

//观察,递推 
#include <iostream>
using namespace std;

int main(){
	int T,N;
	long long a[35]={0,1,3};
	cin>>T; 
	while(T--){
		cin>>N;
		for(int i=3;i<=35;i++){
			if(i%2==1)a[i]=2*a[i-1]-1;
			else a[i]=4*a[i-2]-1;
		}
		cout<<a[N]<<endl;
	}	
	return 0;
} 

  

HDU 2501 [Tiling_easy version] 递推