时间限制: 1000 ms 内存限制: 65535 K
问题描述
一只鼹鼠想要探索北方的一块草地，这块草地是一个无限大的方格矩阵，由于地鼠只会往前不会后退，所以他只会朝北或者东、西方向刨。由于刨过的地方已不是土地，所以不会再次进入这个方格。现在这只鼹鼠打算刨n步，它想要知道能有多少种刨的方案，你能帮他算算吗？注：只要有任何的不同，就算是不同的刨法。
输入
有多组输入，每组是一个整形n，代表刨的步数，1<= n <= 100。
输出
对于每组输入，输出总的方案数。
样例输入
1
2
样例输出
3
7
提示
无来源
小白菜
思路 ： 很明显 他只能往3个方向走 假设 他只能往 前 和 上下走 我们用箭头标注每一步从某处走到某处 假设上一步往前的个数为s3(下一步能走3个方向) 往上和往下的和为s2（下一步能走2个方向） 那么对于下一次 每个往前的可以为s2增加2个 每个 往上和往下的可以产生一个往前的 由此 可知
s3[i]=s2[i-1]+s3[i-1];
s2[i]=s3[i-1]*2+s2[i-1];
ans[i]=s2[i]+s3[i];本题的坑在于 用 int 会爆掉 用 long long会爆掉 用unsigned long long 也会爆掉 用unsigned long long 千万要注意 如果最大的数据看着不是负数并不代表不会爆掉 此时一定要多输入几个数 看看那些数是否爆掉 或者是否比最大数据对应的值更加大一些 做题一定要细心 所以只有用大数去做了 注意 用大数并不难 大数不是很复杂 不要怕大数 就是普普通通的模拟 不要被它的面具吓到 看看拍出来后 多简单啊 自己可一定要征服大数
[cpp]
#include
#include
int s2[111][100],s3[111][100],ans[111][100];
void solve( int str[],int ss[],int sss[])
{
int i;
for(i=0;i<100;i++)
{
str[i]+=(ss[i]+sss[i]);
if(str[i]>=10)
{
str[i+1]=str[i]/10;
str[i]=str[i]%10;
}
}
}
void solve2(int str[],int sss[],int ss[])
{
int i;
for(i=0;i<100;i++)
sss[i]=sss[i]*2;
for(i=0;i<100;i++)
{
str[i]+=(sss[i]+ss[i]);
if(str[i]>=10)
{
str[i+1]=str[i]/10;
str[i]=str[i]%10;
}
}
}
void print(int s[])
{
int i;
for(i=99;i>=0;i--)
if(s[i]!=0) break;
while(i>=0)
{
printf("%d",s[i]);
i--;
}
printf("\n");
}
int main()
{
int n,i;
s2[1][0]=2;
s3[1][0]=1;
ans[1][0]=3;
for(i=2;i<=100;i++)
{
solve(s3[i],s2[i-1],s3[i-1]);
solve2(s2[i],s3[i-1],s2[i-1]);
solve(ans[i],s2[i],s3[i]);
/*a3[i]=a2[i-1]+a3[i-1];
a2[i]=a3[i-1]*2+a2[i-1];
ans[i]=a2[i]+a3[i];*/
}
while(scanf("%d",&n)!=EOF)
{
print(ans[n]);
}
return 0;
}