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

副标题#e#

Problem 1147 Tiling

Time Limit: 1000 mSec??

??Memory Limit : 32768 KB

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

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

?Problem Description

In how many ways can you tile a 2xn?rectangle by 2×1 or 2×2 tiles?

Here is a sample tiling of a 2×17 rectangle.



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


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

?Input

Input is a sequence of lines,each line containing an integer number?
0 <= n <= 250.

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

?Output

For each line of input,output one integer number in a separate line giving the number of possible tilings of a 2x
n?rectangle.

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

?Sample Input

2

8

12

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

?Sample Output

3

171

2731

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

?Source

Albert 2001

? ? ? ? 在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("1\n");
        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;
}

代码二(AC):

#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("1\n");
           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;
}

? ?还试过输出%04d的,在进位的时候除以10000和对10000取余就好了,只要特判0,用祥琨大神的话来说怎么写怎么过;

#p#副标题#e##p#分页标题#e#

? 原谅我对这题说了这么多废话,博主此刻心无法平静,是我太年轻了, 没有阅历,没有胆识,更没有能力。。。

相关文章

发表回复

您的电子邮箱地址不会被公开。