ZZULIOJ 2121

ゝ一纸荒年。 2022-06-17 05:39 80阅读 0赞

## 2121: 爬楼梯 ##

Time Limit: 1 Sec   Memory Limit: 128 MB  
Submit: 292   Solved: 148  
  
[Submit][] [Status][] [Web Board][]

## 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 ##

4 5 6

## Sample Output ##

2184

数学题，找规律，最终的规律的是a\[i\]=a\[i-1\]+a\[i-2\]+a\[i-3\];

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n;
        int b[51];
        int a[21];
        a[0]=1;
        a[1]=1;
        a[2]=2;
        for(int i=3;i<=20;i++)
        {
            a[i]=a[i-3]+a[i-2]+a[i-1];
        }
        scanf("%d",&n);
        int sum,m;
        while(n--)
        {
            scanf("%d",&m);
            sum=1;
            for(int i=1;i<m;i++)
            {
                scanf("%d",&b[i]);
                sum=sum*a[b[i]];
                if(sum>10007)
                {
                    sum=sum%10007;
                }
            }
            printf("%d\n",sum);
        }
        return 0;
    }

[Submit]: https://acm.zzuli.edu.cn/zzuliacm/submitpage.php?id=2121
[Status]: https://acm.zzuli.edu.cn/zzuliacm/problemstatus.php?id=2121
[Web Board]: https://acm.zzuli.edu.cn/zzuliacm/bbs.php?pid=2121