Old MacDonald Had A Farm——递推

分手后的思念是犯贱 2022-06-16 04:46 98阅读 0赞

Think：  
1第m个年头开始表示中间相差m-1年，即当前年数等于上一年和m-1年前的和

Old MacDonald Had A Farm  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
Old MacDonald Had A Farm, cycyk~  
老麦克唐纳德有一个农场，农场里有马、兔、牛三种动物。开始时他有母马、母兔、母牛各 1 只。  
对于每头母马，它从第二年起每年年初生一头小母马。每头小母马从第二个年头开始，每年年初也生一头小母马。  
对于每只母兔，它从第二年起每年年初生一只小母兔。每只小母兔从第三个年头开始，每年年初也生一只小母兔。  
对于每头母牛，它从第二年起每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。  
现在老麦克唐纳德想知道，第 n 年时他总共有多少只动物（这里只考虑母马、母兔和母牛）？

Input  
输入数据有多组（数据组数不超过 100），到 EOF 结束。  
对于每组数据，输入 1 行，包含 1 个整数 n (1 <= n <= 30)，表示询问的年数。

Output  
对于每组数据，输出 1 行，包含 1 个整数，表示答案。

Example Input  
1  
2  
3  
4

Example Output  
3  
6  
10  
17

Hint  
第 1 年时，老麦克唐纳德有母马 1 头、母兔 1 只、母牛 1 头。  
第 2 年时，老麦克唐纳德有母马 2 头、母兔 2 只、母牛 2 头。  
第 3 年时，老麦克唐纳德有母马 4 头、母兔 3 只、母牛 3 头。  
第 4 年时，老麦克唐纳德有母马 8 头、母兔 5 只、母牛 4 头。

Author  
bLue

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        long long a[44], b[44], c[44];
        int n, i;
        a[1] = 1;
        for(i = 2; i <= 30; i++)
            a[i] = 2*a[i-1];
        b[1] = 1;
        b[2] = 2;
        for(i = 3; i <= 30; i++)
            b[i] = b[i-1] + b[i-2];
        c[1] = 1;
        c[2] = 2;
        c[3] = 3;
        for(i = 4; i <= 30; i++)
            c[i] = c[i-1] + c[i-3];
        while(scanf("%d", &n) != EOF){
        
            printf("%lld\n", a[n]+b[n]+c[n]);
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 208KB
    Submit time: 2017-05-05 17:17:12
    ****************************************************/