Problem : Insect Reproduction / 昆虫繁殖

版权信息： 本题考察递归与动态规划的应用，通过模拟昆虫的繁殖过程来求解成虫的总数。

任务总览

题目描述

科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过 x 个月产 y 对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵 (过 x 个月产卵)，问过 z 个月以后共有成虫多少对？

输入格式

输入三个整数 x, y, z，分别表示每对成虫产卵的周期（月），每对成虫每次产卵的数量，以及经过的总月份。

输入范围

• 1 ≤ x ≤ 20
• 1 ≤ y ≤ 20
• x < z ≤ 50

输出格式

输出一个整数，表示经过 z 个月以后，成虫的总对数。

输入输出示例

输入示例 1

1 2 8

输出示例 1

37

解释：

• 初始时只有1对成虫。
• 第1个月：1对成虫。
• 第2个月：1对成虫和2对卵。
• 第3个月：1对成虫，2对卵，且2对卵长成2对成虫。
• 第4个月：1对成虫，2对卵，2对成虫，每对成虫都产2对卵。
• 继续按照此规则直到第8个月，最终成虫对数为37。

解题思路

本题可以通过动态规划或模拟来解决。考虑到每个月的成虫数量取决于之前的成虫数量和卵的生长周期，我们可以定义一个数组来记录每个月成虫的数量。

• ​状态定义​：dp[i] 表示第 i 个月时的成虫对数。
• 初始条件：第1个月只有1对成虫，即 dp[1] = 1。
• 从第2个月开始，根据之前的成虫数量计算新一月的成虫数量。
  • 每对成虫每隔 x 个月会产 y 对卵，每对卵两个月后变成成虫。
• 通过循环模拟每个月的变化，最终得到第 z 个月的成虫对数。

时间复杂度分析

本题的时间复杂度是O(z)，由于z的最大值为50，计算量非常小，因此可以在规定时间内完成。

结论

本题通过模拟昆虫的繁殖过程，使用动态规划或递归的方法，成功求解出经过 z 个月后的成虫总对数。