HDU 2018 母牛的故事

题意

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

解题思路

这个写一写前几项，就能发现规律（但是我不会证明），\(，dp[i]=dp[i-1]+dp[i-3]，i>=4\)，类似于斐波那契额数列

前几项都是\(dp[i]=i, i<=3\)。

最后不要忘记打表，因为是多组样例测试，否者会超时的。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=60;
int ans[maxn];
int main()
{
    int n,m;
    for(int i=1; i<=3; i++)
        ans[i]=i;
    for(int i=4; i<=55; i++)
        ans[i]=ans[i-1]+ans[i-3];
    while(scanf("%d",&n) && n!=0)
    {
        printf("%d\n", ans[n]);
    }
    return 0;
 } 

HDU 2018 母牛的故事

原文：https://www.cnblogs.com/alking1001/p/11875956.html