1004: [递归]母牛的故事 C++丐版斐波那契打表题解

解题思路:看清楚题目就能明白这是一个魔改版的兔子(Fibonacci)数列,我愿称之为母牛数列

我们不去深究到底是如何是如何魔改的(因为太懒了不想去想),只需要要知道,母球们发育周期为四年,而

第N年的母牛总数cnt =  成熟母牛数record[3].num+第三年成长期母牛数record[2].num+ 第二年成长期母牛数record[1].num + 新出生母牛数record[0].num

                                     第三年成长期母牛数record[2].num = 上一年第二年成长期母牛数record[1].num

                                     第二年成长期母牛数record[1].num = 上一年新出生母牛数recore[0],num

                                     新出生母牛数record[0].num = 上一年的成熟母牛数record[3].num

                                     当然这个结构体完全没有必要

然后使用map容器记录第N年中母牛的总数cnt

最后在n次询问中查询map中的记录即可

注意事项:第一次写看都没看直接用队列了QAQ,结果空间时间全部爆炸,

参考代码:

#include<bits/stdc++.h>
using namespace std;

struct cow{
    int num;
}record[4];

map<int,int>m;

void func(int year){
    if(year>55){    //题目给出的年份最大值为55
        return;
    }
    record[3].num += record[2].num;
    record[2].num = record[1].num;
    record[1].num = record[0].num;
    record[0].num = record[3].num;
    m[year] = record[0].num + record[1].num + record[2].num + record[3].num;    //用map记录
    func(year+1);
}
int main(){
    record[0].num = 0;
    record[1].num = 0;
    record[2].num = 0;
    record[3].num = 1;    //设初始有一头成熟母牛
    func(2);       //从第二年开始递归
    m[1]=1;        //设第一年母牛数量为1
    int N;
    while(cin>>N){
        if(N==0)
            return 0;
        cout<<m[N]<<endl;
    }
    return 0;
}