一本通-1312：【例3.4】昆虫繁殖（动态规划）

【题目描述】 科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过x个月产y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)，问过Z个月以后，共有成虫多少对？0≤X≤20,1≤Y≤20,X≤Z≤50。

【输入】 x,y,z的数值。

【输出】 过Z个月以后，共有成虫对数。

【输入样例】 1 2 8

【输出样例】 37

---

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

vector<long long> ovum(55);
vector<long long> insect(55);


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int x, y, z;
    cin >> x >> y >> z;
    for (int i = 1; i <= x; ++i) insect[i] = 1; //前x个月暂无成虫产卵
    for (int i = x + 1; i <= z + 1; ++i) { //问的是z个月以后，其实是第z+1个月
        ovum[i] = insect[i - x] * y;
        insect[i] = insect[i - 1] + ovum[i - 2]; //卵两个月后长成成虫
    }

    cout << insect[z + 1] << endl;

    return 0;
}

这道题目还是很典型的，需要正确计算卵和成虫，另外，题目问的是z月后，问的是第z+1个月的数量，注意问法。另外，这道题目明确指出2个月后长成成虫，其实这个也可以变成一个变量，修改的只是递推关系式里面的计算成虫数量的部分。还有一点是数据类型是long long