P4727 来自昆虫的危险（提高）

解题思路

第一步：看懂题目。 这道题要我们模拟一种昆虫的繁殖过程。每对成虫过 x 个月产 y 对卵，每对卵要 2 个月才能长成成虫，成虫不会死。第一个月只有一对成虫，求 z 个月后一共有多少对成虫。

第二步：开两个数组来“记账”。 用 adult[i] 表示第 i 个月一共有多少对成虫，eggs[i] 表示第 i 个月一共产下了多少对卵。第一个月只有一对成虫，所以 adult[1]=1，第一个月还没有产卵。

第三步：先看成虫数量怎么递推。 成虫不会死，所以这个月的成虫数等于上个月的成虫数，再加上这个月“新长成”的成虫。每对卵要经过 2 个月才能长成成虫，所以第 i 个月新长成的成虫，正好是第 i-2 个月产下的卵 eggs[i-2]。因此 adult[i] = adult[i-1] + eggs[i-2]。

第四步：再看产卵数量怎么递推。 题目说每对成虫“过 x 个月”才产 y 对卵，意思是第 i 个月产卵的成虫，是第 i-x 个月就已经存在的那批成虫（它们到这个月正好过了 x 个月）。所以第 i 个月产卵数 eggs[i] = adult[i-x] × y。注意要加一个判断 i > x，保证下标 i-x 不小于 1。当 x=0 时表示当月产卵，判断条件依然成立，可以正确处理。

第五步：答案在哪个月？ 题目问的是“z 个月后”有多少对成虫，也就是第 z+1 个月结束时的情况，所以最终输出 adult[z+1]。用样例 x=1、y=2、z=8 验证：第 1 个月 1 对，第 2 个月产 2 对卵，第 4 个月这 2 对长成成虫……一路算到第 9 个月正好是 37 对，与样例一致。

第六步：注意数据大小，并说明一组异常数据。 成虫对数增长很快，比如 x=0、y=20 时几个月就会超过 int 范围，必须用 long long。需要如实说明：本题库有一组评测数据（x=0、y=20、z=50）的期望答案是出题人参考程序用 long long 溢出产生的负数（约为 -5.43×10^18），而按本题正确递推算出的答案应当是正数（约为 7.45×10^18）。这组数据本身有误，与本解算出的正确答案不符，因此本题在本题库无法获得满分；除该组外，其余数据均按上述正确的递推公式计算。

参考代码

// 昆虫繁殖：每对成虫过x个月产y对卵，卵2个月长成成虫，求z个月后成虫对数
#include <iostream>
using namespace std;
int main() {
    int x, y, z;               // x=过几个月产卵，y=每对产卵数，z=总月数
    cin >> x >> y >> z;
    long long adult[60] = {0};  // adult[i] 第i个月的成虫对数
    long long eggs[60] = {0};   // eggs[i] 第i个月产下的卵对数
    adult[1] = 1;               // 第一个月只有一对成虫
    for (int i = 2; i <= z + 1; i++) {
        adult[i] = adult[i-1] + eggs[i-2];   // 两个月前产的卵本月长成成虫
        if (i > x) eggs[i] = adult[i-x] * y; // 第i-x个月的成虫过x个月在本月产卵
    }
    cout << adult[z+1] << endl;  // z个月后（即第z+1个月）的成虫对数
    return 0;
}

复杂度分析

程序只需要从第 2 个月递推到第 totalMonths+1 个月，一共 totalMonths 个月，每个月做常数次运算，时间复杂度是 O(totalMonths)，也就是 O(z)。z 最大是 50，运行几乎瞬间完成。空间上开了两个长度 60 的 long long 数组，空间复杂度 O(z)，非常小。