poj 2506 Tiling 【大数】

Description

Input

Output

Sample Input

2
8
12
100
200

Sample Output

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

?

?

坑，0的时候输出1：

?

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<queue>
#include<stack>
#include<algorithm>
#define MAX 1000+10
using namespace std;
int dp[300][MAX];
void ans(int n)//求dp[n]*2; 
{
    int i,j,t=0;
    for(i=0;i<MAX;i++)
    {
        t=dp[n][i]*2+t;
        dp[n][i]=t%10;
        t/=10;
    }
}
int main()
{
    int n,m,i,j;
    int k;
    while(scanf("%d",&n)!=EOF)
    {
        memset(dp,sizeof(dp));
        dp[0][0]=1;
        dp[1][0]=1;dp[2][0]=3;
        if(n<3)
        {
            printf("%dn",dp[n][0]);
            continue;
        }
        for(i=3;i<=n;i++)
        {
            ans(i-2);
            for(j=0;j<MAX;j++)
            {
                dp[i][j]+=dp[i-1][j]+dp[i-2][j];
                if(dp[i][j]>=10)
                {
                    dp[i][j+1]+=1;
                    dp[i][j]-=10;
                }
            }
        }
        for(i=MAX-1;i>=0;i--)
        if(dp[n][i]!=0)
        break;
        for(;i>=0;i--)
        printf("%d",dp[n][i]);
        printf("n");
    }
    return 0;
}

?更新：2015.8.22

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int a[260][2010];
int len[260];
int main()
{
    memset(a,sizeof(a));
    a[0][0] = 1,len[0] = 1;
    a[1][0] = 1,len[1] = 1;
    a[2][0] = 3,len[2] = 1;
    int temp;
    for(int i = 3; i < 251; i++)
    {
        int l1 = len[i-1];
        int l2 = len[i-2];
        temp = 0;
        for(int j = 0; j < l1; j++)
        {
            if(j >= l2)
                temp += a[i-1][j];
            else
                temp += 2 * a[i-2][j] + a[i-1][j];
            a[i][j] = temp % 10;
            temp /= 10;
        }
        while(temp)
        {
            a[i][l1++] = temp % 10;
            temp /= 10;
        }
        len[i] = l1;
    }
    int N;
    while(scanf("%d",&N) != EOF)
    {
        for(int i = len[N]-1; i >= 0; i--)
            printf("%d",a[N][i]);
        printf("n");
    }
    return 0;
}