昆虫繁殖

时间限制：C/C++ 1000MS，其他语言 2000MS
内存限制：C/C++ 256MB，其他语言 512MB

描述

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

输入描述

\(x,y,z\)的数值。

输出描述

过 \(Z\) 个月以后，共有成虫对数。

用例输入 1

1 2 8

用例输出 1

37

用例输入 2

5 13 39

用例输出 2

847289

提示

样例解释：1 2 8

第一次产卵时间：第 \(2\) 个月产卵 \(2\) 对，随后每个月均可产卵
另：本题测试数据偏弱，无需考虑高精度

代码

DFS 做法

#include<cstdio>
using namespace std;

long long f[55];
int x,y,z;

void DFS(int ti,long long ins)
{
	f[ti]+=ins;
	for(int i=ti+x+2;i<=z+1;i+=x)
		DFS(i,ins*y);
	return;
}

int main()
{
	scanf("%d%d%d",&x,&y,&z);
	DFS(1,1);
	long long ans=0;
	for(int i=1;i<=z+1;i++)
		ans+=f[i];
	printf("%lld\n",ans);
	return 0;
}

动态规划 做法

#include<cstdio>
#define int long long
using namespace std;

int cnt=1;
int bug[5][55];
int inc[5];

signed main()
{
	int x,y,z;
	scanf("%lld%lld%lld",&x,&y,&z);
	bug[1][1]=1,bug[2][1]=x;
	for(int ti=1;ti<=z;ti++)
	{
		inc[0]=inc[1];
		inc[1]=inc[2];
		inc[2]=0;
		for(int i=1;i<=cnt;i++)
		{
			bug[2][i]--;
			if(!bug[2][i])
			{
				inc[2]+=bug[1][i]*y;
				bug[2][i]=x;
			}
		}
		if(inc[0])
		{
			bug[1][++cnt]+=inc[0];
			inc[0]=0;
			bug[2][cnt]=x;
		}
	}
	int ans=0;
	for(int i=1;i<=cnt;i++)
		ans+=bug[1][i];
	printf("%lld\n",ans);
	return 0;
}