Tiling a Grid With Dominoes
Time Limit: 1000/500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 404 Accepted Submission(s): 316
Problem Description
We wish to tile a grid 4 units high and N units long with rectangles (dominoes) 2 units by one unit (in either orientation). For example, the figure shows the five different ways that a grid 4 units high and 2 units wide may be tiled.
Write a program that takes as input the width, W, of the grid and outputs the number of different ways to tile a 4-by-W grid.
Input
The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.
Each dataset contains a single decimal integer, the width, W, of the grid for this problem instance.
Each dataset contains a single decimal integer, the width, W, of the grid for this problem instance.
Output
For each problem instance, there is one line of output: The problem instance number as a decimal integer (start counting at one), a single space and the number of tilings of a 4-by-W grid. The values of W will be chosen so the count
will fit in a 32-bit integer.
will fit in a 32-bit integer.
Sample Input
3 2 3 7
Sample Output
1 5 2 11 3 781
Source
Recommend
题意：
有一块4*N(1 ≤ N ≤ 1000)的矩形区域。你只有1*2的地砖。问你铺满这块区域有多少种方法。
思路：
对于铺砖问题。我们可以一行一行的分析即一行一行的铺。由于只有1*2的砖。所以当前处理行只会受到上一行的影响。上上行肯定影响。不了了。这个画下图就知道了。所以对于当前处理行的状态我们可以用01序列来表示。第i位为1表示第i个位置会占用下一行的位置。即砖是竖着放的。0表示不占用下一行的位置。0肯定是成对出现的。因为横放的话需要两个位置。分析到这里后。基本算法就出来了。用dp[i][s]表示处理完前i行。第i行状态为s的方法数。s为01序列的十进制表示。然后我们可以根据s用dfs构造出一个可行状态ss。那么dp[i+1][ss]+=dp[i][s]。所以我们只需要枚举第i行状态推i+1行就可以了。最后只要输出dp[N][0]就行了。因为最后一行不能占用下一行的位置了。
详细见代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string>
#include<queue>
#include<set>
#include<map>
//#pragma comment(linker,"/STACK:1024000000,1024000000")
using namespace std;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const double PI=acos(-1.0);
const int maxn=100010;
//typedef __int64 ll;
int dp[25][16];
void dfs(int s,int ss,int p,int dep)//s为当前行状态。ss为构造的下一行状态。p为处理到第几列。dep为列。
{
if(p>3)//一行处理完了。
{
dp[dep+1][ss]+=dp[dep][s];
return;
}
if(s&(1<<p))
dfs(s,ss,p+1,dep);//已被上一行占用直接跳过
else
{
dfs(s,ss|(1<<p),p+1,dep);//竖着放
if(p<=2&&!(s&(1<<(p+1))))//横着放
dfs(s,ss,p+2,dep);
}
}
int main()
{
int i,j,n,t,cas=1;
memset(dp,0,sizeof dp);
dp[0][0]=1;
for(i=0;i<25;i++)//经计算最多为21行。不让就超过int范围了。
for(j=0;j<16;j++)
if(dp[i][j])
dfs(j,0,0,i);
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%d %d\n",cas++,dp[n][0]);
}
return 0;
}
该题与poj上一题类似。可以练习下。题目