2017广东工业大学程序设竞赛C题爬楼梯

Description

小时候,我只能一阶一阶得爬楼梯,

后来,我除了能一次爬一阶,还可以一次爬两阶,

到现在,我最多一次可以爬三阶。

那么现在问题来了,我想爬上n层楼,相邻楼层之间有一段楼梯,虽然我一次可以爬1个台阶、2个台阶和3个台阶,但是我在i与i+1层之间的楼梯上时,我不能跨越到i+1与i+2层之间的楼梯。现在有个n层的楼,知道每一段楼梯的阶数,我想知道,如果我只会往上走,并且忽略其他不在楼梯上的其他移动,共有多少种方案可以到达第n层。

Input

第一行一个整数T(0<T<=50)表示有多少组样例。

对于每一组样例:

第一行一个n(1<n<=50)表示有多少层楼。

接下来一行,包括n-1个整数xi(0<xi<=20),由下到上依次表示每段楼梯的长度。

Output

对于每组数据,输出一行表示共有多少种方案。由于答案较大,所以输出答案请对10007取模。

Sample Input

2
2
3
4
4 5 6

Sample Output

4
2184
 
此题类型 简单dp
 
AC代码
 #include<stdio.h>
int main()
{
int f[];
int i,j,T,n,x,ans;
f[]=;
f[]=;
f[]=;
f[]=;
for(i=; i<=; i++)
{
f[i]=f[i-]+f[i-]+f[i-];
f[i]%=;
}
scanf("%d",&T);
while(T--)
{
ans=;
scanf("%d",&n);
for(i=; i<n; i++)
{
scanf("%d",&x);
ans=(ans*f[x])%;
}
printf("%d\n",ans);
} return ;
}
上一篇:iOS企业应用Profile制作流程


下一篇:node path的几个路径问题