首页 > ACM题库 > HDU-杭电 > hdu 1992 Tiling a Grid With Dominoes-动态规划-[解题报告]C++
2013
12-26

hdu 1992 Tiling a Grid With Dominoes-动态规划-[解题报告]C++

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列的话,当然dp[n] + =dp[n-1] ,如果只加入2列的话,并且不以前一个为后缀的话就只有四个,在递推加入3列的情况,并且不以前第1个和第2个为后缀,我们分一下三种情况讨论:

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

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

  3) 如果都是横着的,那么必然以加入2列的情况重合;

同理减少偶数列 dp[n]+=3*dp[i];

#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;
}

解题转自:http://blog.csdn.net/struggle_mind/article/details/7642859


  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!