poj 2506 Tiling 递推

题目链接：

　　http://poj.org/problem?id=2506

题目描述：

　　有2*1和2*2两种瓷片，问铺成2*n的图形有多少种方法？

解题思路：

　　利用递推思想，2*n可以由2*（n-1）的状态加上一块竖放2*1的瓷片转移得来，也可以由2*（n-2）的状态加上一块2*2的瓷片或者加上两块横放的2*1的瓷片转移得来。

可得出递推公式：dp[n] = dp[n-1] + dp[n-2]*2；

ac秘诀：

　　（1）：从输出样例可以看出要用大数来表示，大概需要90位左右。

　　（2）：2*0不是零种方法吗？经过无数次wa，证明是一，竟然是一！！！！！！！，也是醉了，苦苦思索了良久··········。

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 using namespace std;

 #define maxn 90

 int dp[][maxn], a[maxn];

 int main ()

 {

     int n, i, j;

     memset (dp, , sizeof(dp));

     dp[][] = ;

     dp[][] = ;

     dp[][] = ;

     for (i=; i<; i++)//打标，储存所有的结果

     {

         int yu = ;

         for (j=; j<maxn; j++)//大数运算

         {

             int s = dp[i-][j]* + yu + dp[i-][j];

             dp[i][j] = s % ;

             yu = s / ;

         }

     }

     while ( scanf ("%d", &n) != EOF)

     {

         i = maxn - ;

         while (dp[n][i] == )//除去前导零

             i--;

         for (; i >=; i--)

             printf ("%d", dp[n][i]);

         printf ("\n");

     }

     return ;

 }

巴特西

poj 2506 Tiling 递推

最新文章

热门文章