首页 > ACM题库 > HDU-杭电 > hdu 2501 Tiling_easy version-动态规划-[解题报告]C++
2014
02-09

hdu 2501 Tiling_easy version-动态规划-[解题报告]C++

Tiling_easy version

问题描述 :

有一个大小是 2 x n 的网格,现在需要用2种规格的骨牌铺满,骨牌规格分别是 2 x 1 和 2 x 2,请计算一共有多少种铺设的方法。

输入:

输入的第一行包含一个正整数T(T<=20),表示一共有 T组数据,接着是T行数据,每行包含一个正整数N(N<=30),表示网格的大小是2行N列。

输出:

输入的第一行包含一个正整数T(T<=20),表示一共有 T组数据,接着是T行数据,每行包含一个正整数N(N<=30),表示网格的大小是2行N列。

样例输入:

3
2
8
12

样例输出:

3
171
2731

2011-12-15 04:01:32

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

题意:中文。。

mark:递推又见递推。dp[i] = dp[i-1] + dp[i-2]*2。

代码:

# include <stdio.h>


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


int main ()
{
    int i, T ;
    for (i = 2 ; i<= 30 ; i++)
        dp[i] = dp[i-1] + dp[i-2]*2 ;
    scanf ("%d", &T) ;
    while(~scanf ("%d", &T))
        printf ("%d\n", dp[T]) ;
    return 0 ;
}

解题转自:http://www.cnblogs.com/lzsz1212/archive/2012/01/06/2314665.html


  1. #include <cstdio>

    int main() {
    //answer must be odd
    int n, u, d;
    while(scanf("%d%d%d",&n,&u,&d)==3 && n>0) {
    if(n<=u) { puts("1"); continue; }
    n-=u; u-=d; n+=u-1; n/=u;
    n<<=1, ++n;
    printf("%dn",n);
    }
    return 0;
    }

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。