FZU- Problem 1147 Tiling，递推坑题，大数水过~~

Time Limit: 1000 mSec??

??Memory Limit : 32768 KB

http://acm.fzu.edu.cn/problem.php?pid=1147

?Problem Description

In how many ways can you tile a 2xn?rectangle by 2x1 or 2x2 tiles?

Here is a sample tiling of a 2x17 rectangle.

?Input

?Output

?Sample Input

?Sample Output

?Source

? ? ? ? 在HDU上做过原题，只不过题目数据范围没有这么大，开始一看，激动坏了，递推数列一打，样例水过，直接交WA，然后试试数据发现连long long 都会爆，那就是大数加法了，可是按理大数用二维数组存一下也没什么问题，运行都是完全正确，提交WA了6次，各种方法都试了，WA；

? ? ? ? ? 最开始用大数做的时候问队友0的情况，按理输入0输出也是0，杭电上都是数组清0,然后从三开始打表a[i]=a[i-1]+2*a[i-2];这样0就是0，后来才知道0的情况是1，我那个没脾气了，，，你这题这么坑你爸妈知道吗，啊！！我WA了6遍，5个小时没A出这个题，我当时很肯定地对队友说表肯定没错，运行完全正确，可是不造为什么就是WA,还以为大数这里搞错了，，也质疑过0的情况有坑，但我还是没改，因为我本质也是觉得0就是输出0，结果。。。。。。。。。。

? ? ?建议先去HDU上把这个题A了点击-原题，没什么技巧，博主比较笨，当时做的时候多列了几个样例就发现了规律，这里不过是用大数罢了，但注意特判0，代码拿去：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=251;
int a[N][N];
int main()
{
    int n,i,j;
    memset(a,sizeof(a));
    a[1][0]=1,a[2][0]=3;
    int c=0;
    for(i=3;i<=N;i++)
    {
        c=0;
        for(j=0;j<=N;j++)
        {
            a[i][j]=a[i-1][j]+2*a[i-2][j]+c;
            c=a[i][j]/100;
            a[i][j]%=100;
        }
    }
    while(~scanf("%d",&n))
    {
        if(n==0)
            printf("1n");
        else
        {
            for(j=250;j>=0;j--)
                if(a[n][j])
                break;
                 printf("%d",a[n][j]);
            for(i=j-1;i>=0;i--)
                printf("%02d",a[n][i]);
            printf("n");
        }
    }
    return 0;
}

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=260;
int a[N][100];
int main()
{
    int n,sizeof(a));
    a[1][0]=1;
    a[2][0]=3;
    int c=0;
    for(i=3;i<=N;i++)
    {
        c=0;
        for(j=0;j<=100;j++)
           {
               a[i][j]=a[i-1][j]+2*a[i-2][j]+c;
               c=a[i][j]/10;
               a[i][j]%=10;
           }
    }
       while(~scanf("%d",&n))
       {
           if(n==0)
            printf("1n");
           else
           {
               for(i=99;i>=0;i--)
                if(a[n][i])
                break;
               for(j=i;j>=0;j--)
                printf("%d",a[n][j]);
               printf("n");
           }
       }
       return 0;
}

（编辑：济源站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!