动态规划 专题

HDU 2018 母牛的故事

题目描述

输入输出样例

思路

因为本题数据比较弱，可以采用打表，直接输出。

先找规律，n <= 4 时，母牛数量就是年份。之后，就是前一年数量加上前三年的数量（因为此时最先出身的小母牛也开始生小母牛了），即 a[i] = a[i - 1] + a[i - 3] 。

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

int main()
{
    int a[100],n;
	a[0] = 0;
	a[1] = 1;
	a[2] = 2;
	a[3] = 3;
	//打表 
	for (int i = 4; i < 55; i++) {
		a[i] = a[i - 1] + a[i - 3];
	}
	while (scanf("%d", &n) != EOF && n != 0) {
		printf("%d\n", a[n]);
	}
	return 0;
}