首页 > ACM题库 > HDU-杭电 > HDU 1143 Tri Tiling-动态规划-[解题报告] C++
2013
11-28

HDU 1143 Tri Tiling-动态规划-[解题报告] C++

Tri Tiling

问题描述 :

In how many ways can you tile a 3xn rectangle with 2×1 dominoes? Here is a sample tiling of a 3×12 rectangle.

输入:

Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 ≤ n ≤ 30.

输出:

For each test case, output one integer number giving the number of possible tilings.

样例输入:

2
8
12
-1

样例输出:

3
153
2131

2011-12-20 17:54:28

地址:http://acm.hdu.edu.cn/showproblem.php?pid=1143

题意:用2*1的砖铺3*n,有多少种方法。

mark:递推。dp[n] = 4*dp[n-2]-dp[n-4]

代码:

# include <stdio.h>


int dp[35] = {1, 0, 3, 0} ;


int main ()
{
    int i, n ;
    for (i = 4 ; i<= 30 ; i+= 2)
        dp[i] = 4*dp[i-2] - dp[i-4] ;

    while (~scanf ("%d", &n))
    {
        if (n < 0) break ;
        printf ("%d\n", dp[n]) ;
    }
    return 0 ;
}


  1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  2. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;