zzuli 1981 赛前的准备--忙里偷闲 2/5

题目链接

题目描述

小明身为志愿者的一员，已经连续劳动了好长时间。趁着休息的时候，爱玩游戏的小明打开炉石传说，趁着休息的时间赶紧玩上一把。小明在玩的时候发现一个问题。
众所周知，奴隶主受到伤害后如果不死会召唤一个满血的奴隶主（每一个满血的奴隶主只有三点血）。现在假设场上可以存在无限个奴隶主，用旋风斩可以对所有奴隶主造成一点伤害，这样不死的奴隶主会再次召唤一个满血的奴隶主。 假设场上只有一个奴隶主，现在问经过n次旋风斩场上有多少奴隶主。

输入

多组测试数据。
每组测试数据一个正整数n，表示经过n次旋风斩（0<=n<=1000）。

输出

对于每组测试数据，输出经过n次旋风斩场上的奴隶主的数量（结果对1000000007取余）。

样例输入

0
1

样例输出

1
2

题意看起来是一个模拟题，简单推算一下会发现到后边奴隶主会太多。那么还是先模拟一下吧，开了二百万的数组，每个元素代表一个奴隶主的血量，然后按照题意模拟，欸，怎么和斐波那契数列这么像，n>=3时，f(n)=f(n-1)+f(n-2);

OK，规律找出来了，这就是一道水题啦，速度过掉

#include<stdio.h>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int a1[1011];

int main()
{

    int n;


    a1[0]=1;
    a1[1]=2;
    a1[2]=4;
    for(int k=3; k<1004; k++)
    {
        a1[k]=a1[k-1]+a1[k-2];
        a1[k]%=1000000007;

    }
    while(scanf("%d",&n)!=EOF)
        if(n>0)
            printf("%d\n",a1[n]);
        else
            printf("1\n");



    return 0;
}

                                                                                                                      2018年10月26号的题解，本周第二篇。