| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 7965 | Accepted: 3866 |
Description
Input
Output
Sample Input
2 8 12 100 200
Sample Output
3 171 2731 845100400152152934331135470251 1071292029505993517027974728227441735014801995855195223534251
算法分析：递推公式：f[i]=f[i-1]+f[i-2]*2; 此公式也不是我自己推导出来的，我也没推导出来，我从ACM之家上的java代码看出的
公式。
代码：
#include <stdio.h>
#include <string.h>
int a[1001][501]={0};
int main()
{
int n;
int i, j, h, e;
a[0][500] = 1;
a[1][500] = 1;
a[2][500] = 3;
for(i=3; i<=250; i++)
{
h = 0;
for(j=500; j>=0; j--)
{
e=a[i-2][j]*2+a[i-1][j]+h;
a[i][j]=e%10;
h=e/10;
}
}
while(scanf("%d", &n)!=EOF)
{
if(n==0)
{
printf("1\n"); continue;
}
i = 0;
while(a[n][i]==0)
{
i++;
}
for(i; i<=500; i++)
{
printf("%d", a[n][i] );
}
printf("\n");
}
return 0;
}
这还有一份java代码，但是提交WA，不知道哪里出了问题。
import java.util.*;
import java.math.*;
public class Main{
static BigInteger[] ans; //
public static void main(String[] args){
Scanner reader=new Scanner(System.in);
ans = new BigInteger[251];
ans[0]=BigInteger.valueOf(1);
ans[1]=BigInteger.valueOf(2);
ans[2]=BigInteger.valueOf(3);
for(int i=3; i<=250; i++)
{
ans[i] = ans[i-1].add(ans[i-2].multiply(BigInteger.valueOf(2)));
}
int n;
while(reader.hasNextInt()){
n=reader.nextInt();
System.out.println(ans[n]);
}
}
}
POJ 2506 Tiling (递推 + 大数加法模拟 )
原文：http://www.cnblogs.com/yspworld/p/4319839.html