首页 > 代码库 > poj2506（Tiling）

poj2506（Tiling）

2024-07-05 23:19:12   224人阅读

题目大意：

给你一个2*N的矩形。 让你用2*1或者2*2的小矩形去拼成2*N的矩形。问你有多少种拼法。

 

解题思路：

类似于简单的骨牌铺路。

N长度的矩形，可以由  前（N-1）种+最后一个放竖着的2*1小矩形  和  前（N-2）种+最后两位横着放两位2*1的小矩形  和  前（N-2）种+最后两位放一个两位2*2的小矩形。

所以递推公式  f(n)=f(n-1)+f(n-2)+f(n-2).

 

涉及到大数相加。  （需要整理大数相加，大数相减，大数相乘，大数相除的模板！）

 

代码：

 1 #include<cstdio>
 2 #include<math.h>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 int a[255][1000];
 8 void inint()
 9 {
10     int i,j,k;
11     a[0][999]=1;
12     a[1][999]=1;
13     a[2][999]=3;
14     for(i=3;i<255;i++)
15         for(j=999;j>=0;j--)
16         {
17             a[i][j]+=a[i-1][j]+a[i-2][j]+a[i-2][j];
18             if (a[i][j]>=10)
19             {
20                 int t=a[i][j];
21                 a[i][j]=t%10;
22                 a[i][j-1]+=t/10;
23             }
24         }
25 }
26 int main()
27 {
28     memset(a,0,sizeof(a));
29     inint();
30     int n;
31     while(scanf("%d",&n)!=EOF)
32     {
33        int i;
34        int ce=0;
35        for(i=0;i<1000;i++)
36        {
37            if (!ce&&!a[n][i])
38                continue;
39             ce++;
40             printf("%d",a[n][i]);
41        }
42        printf("\n");
43     }
44     return 0;
45 }
View Code

 


联系
我们