C1-F-超体-简单版

题目

题目描述 要么永生，要么繁殖。

在环境舒适的 X 星球，细胞们选择了繁殖，并且把知识一代一代传承下去。

在 t=1 秒时，有一个新生的细胞在混沌中诞生了。

对于每个细胞，当它诞生 a 秒后就会变得成熟。 每个成熟的细胞每秒都会分裂一次（包括它刚刚成熟的那一时刻）。每次分裂会产生一个新生细胞。 每个细胞在它的成熟期只能分裂 b 次。在最后一次分裂之后，细胞会立刻进入衰老期。 进入衰老期再过 c 秒后，细胞会立刻死亡。 在 t=T 秒时，你能计算出 X 星球一共有多少活着的细胞吗？

输入 一行，仅四个整数，相邻整数间由一个空格隔开，四个整数分别是上文中的 a,b,c,T.

输出 一行，仅一个整数，在 t=T 秒时活着的细胞的总数。保证答案在 long long 范围内。

输入样例1 1 1 1 2 输出样例1 2 输入样例2 1 1 1 3 输出样例2 3 输入样例3 1 1 1 5 输出样例3 3 数据范围 a,b,c,T∈[1,10]

思路分析

乍一看这个题貌似是斐波那契数列，但实际上由于本题数据量较小，可以使用其他方法。 由于a，b，c都在[1，10]之间，所以细胞的年龄最大为30，可以使用一个长度为30的数组存储每一个年龄段细胞的数量。

AC代码

#include<stdio.h> long long num[35]={0}; int main() { int i,j,a,b,c,t,len; scanf("%d%d%d%d",&a,&b,&c,&t); len=a+b+c; num[0]=1; for(i=2;i<=t;i++) { for(j=len-1;j>=1;j--) num[j]=num[j-1]; num[0]=0; for(j=a;j<a+b;j++) num[0]+=num[j]; } long long ans=0; for(i=0;i<len;i++) ans+=num[i]; printf("%lld",ans); }