【HDU-2018】解题报告（递推，水题）

原始题目

母牛的故事

  • Time Limit: 2000/1000 MS (Java/Others)
  • Memory Limit: 65536/32768 K (Java/Others)
  • Total Submission(s): 105012
  • Accepted Submission(s): 51527

Problem Description

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

Input

输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。 n=0表示输入数据的结束，不做处理。

Output

对于每个测试实例，输出在第n年的时候母牛的数量。 每个输出占一行。

Sample Input

2
4
5
0

Sample Output

2
4
6

Author

lcy

Source

C语言程序设计练习（三）

Recommend

lcy

题目大意

如题

解题思路

  • \(b[i]\)表示第i年的母牛数，\(s[i]\)表示第i年的小牛数。有\(b[i]=b[i-1]+b[i-3]\);\(s[i]=s[i-1]-b[i-3]+b[i]\);
  • 即第i年的母牛等于i-1年的母牛数加上三年前母牛产的小牛数（今年长成母牛），第i年的小牛数等于第i-1年的小牛数减去三年前新产的小牛数（今年长成母牛）加上今年新产的小牛。
  • 输出大小牛的和 # 解题代码 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <set>
    #include <algorithm>
    #include <queue>
    #include <map>
    #include <string>
    #define eps 1e-8
    #define INF 0x3f3f3f3f
    #define rep(i,a,n) for(int i=a;i<n;i++)
    #define per(i,a,n) for(int i=n-1;i>=a;i--)
    using namespace std;
    const int maxn=1e8+2;
    typedef long long ll;

    int b[100],s[100];
    void solve(){
    	b[1]=b[2]=b[3]=b[4]=1;
    	s[1]=0;
    	s[2]=1;
    	s[3]=2;
    	s[4]=3;
    	for(int i=5;i<55;i++){
    		b[i]=b[i-1]+b[i-3];
    		s[i]=s[i-1]-b[i-3]+b[i];
    	}
    	
    }
    int n;
    int main(){
    	solve();
    	while(cin>>n&&n){
    		cout<<b[n]+s[n]<<endl;
    	}
    }

收获与反思

暂无