递推做法 思路+代码

设$F(n)$为第$n$个月时，成虫的对数
面对这样经典的递推题，还是尝试寻找递推关系

可以注意到：$F(n)$实际上受两个因素影响：

1. 当月会有新成熟的成虫
2. 当月会有从上个月活下来的“老成虫”

可以注意到，当月新成熟的成虫一定是从前$n-x-2$个月的成虫产生的，每对成虫可以产生$y$对卵，则当月新成熟的成虫的个数为$F(n-x-2)*y$

“老成虫”的数量显然为$F(n-1)$

故得，递推关系为：$F(n) = F(n-x-2)*y+F(n-1)$

由于初始的成虫的y对卵，在$1+x$个月后才能成熟，在此之前，$F(n) = 1$
故得，初始条件为：$F(n) = 1,n<=2+x$

总结：

$$\begin{cases} F(n) = y*F(n-x-2)+F(n-1),n>x+2\\ F(n) = 1,n\leq x+2 \end{cases}$$

Warning！！！

题目求的是$z$个月后，由于我们是从第一个月出发，所以求的是$F(z+1)$而不是$F(z)$哦

#include <bits/stdc++.h>
using namespace std;

int x,y,z,a[1000],new_bug[1000];

int main(){

    cin>>x>>y>>z;

    z+=1; // Warning
    a[1] = 1; // Basic condition

    for(int i=2;i<=z;i++){
        if(i<=x+2){ // M3
            a[i] = 1;
            continue;
        }
        a[i] = (a[i-x-2])*y+a[i-1];
    }

    cout << a[z];
    
}