2013
12-26

# Tiling a Grid With Dominoes

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.

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.

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.

3
2
3
7

1 5
2 11
3 781

http://acm.hdu.edu.cn/showproblem.php?pid=1992

1） 如果最后一列是4个都是着的，那么必然以加入1列的情况重合；

2） 如果最后一列是2个横着的，一个竖着的，存在两种情况，就不画图了

3） 如果都是横着的，那么必然以加入2列的情况重合；

#include <cstdlib>
#include <iostream>

using namespace std;

long long dp[1010];

int main(int argc, char *argv[])
{
dp[0]=1;
dp[1]=1;
dp[2]=5;
//dp[3]=11;
for(int i=3;i<=1000;i++)
{
dp[i]=dp[i-1]+4*dp[i-2];
for(int j=3;j<=i;j++)
if(j&1) dp[i]+=2*dp[i-j];
else dp[i]+=3*dp[i-j];
}
int n,cas=1,ca;
cin>>ca;
while(ca--)
{
cin>>n;
cout<<cas++<<" "<<dp[n]<<endl;
}
//system("PAUSE");
return EXIT_SUCCESS;
}

1. Gucci New Fall Arrivals

This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.

2. L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-1]）这个地方也也有笔误
应改为L（X [0 .. M-1]，Y [0 .. N-1]）= 1 + L（X [0 .. M-2]，Y [0 .. N-2]）

3. 网站做得很好看，内容也多，全。前段时间在博客园里看到有人说：网页的好坏看字体。觉得微软雅黑的字体很好看，然后现在这个网站也用的这个字体！nice!