long long supports a maximum of 19 digits if N=5000

0 Answer
long long type also can not save, use high precision addition.
#include
int f[5050][5050];
int len=1;
//本题结果可能很大,正常处理会溢出,故考虑高精度
void deal(int x)
{
for(int i=1;i<=len;i++)//直接处理和
{
f[x][i]=f[x-1][i]+f[x-2][i];
}
for(int i=1;i<=len;i++)//处理进位
{
if(f[x][i]>=10)//必须满足大于等于10
{
f[x][i+1]+=f[x][i]/10;//向高一位进1
f[x][i]=f[x][i]%10;
if(f[x][len+1]) len++;//处理最高到达的位数
}
}
}
int main()
{
int n;
scanf("%d",&n);
f[1][1]=1;
f[2][1]=2;//f[i][j]代表走到第i个楼梯有的方法数
for(int i=3;i<=n;i++)
{
deal(i);
}
for(int i=len;i>=1;i--)//倒叙输出就是值
{
printf("%d",f[n][i]);
}
return 0;
}
这家伙很懒,什么都没留下...