DC1300 昆虫繁殖
大约 4 分钟递推
DC1300 昆虫繁殖
【算法标签】 递推
【语法标签】 :数组、for循环、long long
科学家发现了一种特殊昆虫:
- 每对成虫过 x 个月产 y 对卵
- 每对卵过 2 个月长成成虫
- 卵长成成虫后的第一个月不产卵(需等 x 个月)
- 成虫不死,第一个月已有 1 对成虫(已成熟,可立即产卵)
给定 x, y, z,求 z 个月后共有多少对成虫。
数据范围:,,。
二、解题思路
题目中要求的是 个月后的成虫个数,即第 个月的成虫个数。
我们只需定义一个数组 存储每个月成虫的个数。考虑到每个月会有卵变成新的成虫,所以我们还需定义一个数组 存储每个月的新增卵的数量。
1. 定义两个数组
| 数组 | 含义 | 说明 |
|---|---|---|
a[i] | 第 i 个月末的成虫对数 | a[0] = 1,初始已有 1 对成虫 |
b[i] | 第 i 个月新增的卵的对数 | 当月由成虫产下的卵 |
题目要求"z 个月后",即第 z 个月末的成虫数,答案为
a[z]。
2. 两条递推线
成虫的递推——老成虫不死,卵 2 个月后变新成虫:
- :上个月的成虫全部存活
- :2 个月前产的卵,本月刚好发育为成虫
卵的递推——第 i 个月产的卵,来自 个月时已存在的成虫:
- : 个月时的成虫,到了第 i 个月都已"冷却完毕",具备产卵能力
- 每对产 对卵,所以乘以
3. 初始条件
设 a[0] = 1,表示在第 0 个月(初始状态)就有 1 对已成熟的成虫。
下标为负时值取 0(数组初始化为 0,配合 if (i >= x) 和 if (i >= 2) 判断即可)。
4. 手动模拟样例
样例:x=1, y=2, z=8,答案 37。
计算顺序:先算 a[i],再算 b[i](因为 时 依赖当月成虫数)。
| i | 成虫 | 卵 |
|---|---|---|
| 0 | 1(初始时一对成虫) | — 初始时无卵 |
| 1个月结束 | 第1个月后还没有成虫 | 第一个月结束产了 2 对卵 |
| 2个月结束 | 此时 时产的虫卵还没有变成成虫 | 成虫第一个不产卵,所以不是 ,而是上个月的 |
| 3个月结束 | 即 | |
| 4个月结束 | ||
| 5个月结束 | ||
| 6个月结束 | ||
| 7个月结束 | ||
| 8个月结束 | — |
理解关键:第 个月产卵的是 ( 个月时的成虫),它们到第 个月刚好过完 x 个月的"冷却期",具备产卵能力。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
long long a[55]; // a[i]:第 i 个月末的成虫对数
long long b[55]; // b[i]:第 i 个月新增的卵的对数
int main() {
int x, y, z;
cin >> x >> y >> z;
a[0] = 1; // 初始有 1 对成虫(已成熟)
for (int i = 1; i <= z; i++) {
// 1. 先算成虫:上月成虫 + 2 月前的卵成熟
a[i] = a[i - 1];
if (i >= 2)
a[i] += b[i - 2];
// 2. 再算卵:i-x 个月时的成虫均已冷却完毕
// 注意必须先算 a[i] 再算 b[i],因为 x=0 时 b[i] 依赖 a[i]
if (i >= x)
b[i] = a[i - x] * y;
}
cout << a[z] << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,单层循环,。
- 空间复杂度:,两个数组
a[55]和b[55]。
五、易错点
- 初始成虫已成熟:
a[0] = 1,初始那对成虫已过 x 个月,可直接产卵。 - 计算顺序:必须先算
a[i],再算b[i]。因为 时 ,依赖当月刚算出的 。 - 下标边界: 和 可能为负,必须加
if判断,数组默认值为 0 正好对应"无卵/无成虫"。 - 数据类型:当 x 较小、y 较大时,成虫增长接近指数级,必须用
long long。 - a[i] 和 b[i] 的区别:
a[i]是累积总数,b[i]是当月新增数,不要混淆。
