描述
ZZY领养了一对刚刚出生的不知名小宠物..巨萌巨可爱!!...小宠物的生命为5个单位时间并且不会在中间出意外翘辫子(如: 从0出生能活到5但活不到6)..小宠物经过2个单位时间成熟..刚刚成熟的一对小宠物能立即生育6只新的小宠物(如: 从0出生的一对在2时成熟并进行第一次生育）...小宠物是很忠诚的..不会在中途换伴侣..每对小宠物生育一次这一对的生育能力就会降低2个..也就是说一对小宠物在第二次生育时就只能生4个了..小宠物成熟后每个单位时间都会尽力的生育(例: 从0出生的一对..2时间生6个..3时间生4个..4时间生2个...5时间生不出..6时间这一对已经挂了..)..生育出来的新小宠物会继续这个过程..
ZZY想知道从单位时间0开始..经过M个单位时间(时间为M时)将有多少只活着的小宠物(0时刻有2只小宠物)
因为ZZY隐隐地觉得什么地方怪怪的...所以请将这个数目mod 10000
输入
多组数据读到EOF
每组数据一行:
M ( 0<=M<=2000000000 )
最多500组数据
输出
每组输出一行为 Case 组号: 答案，即M时刻活着的小宠物个数%10000
样例输入
0
1
2
3
4
8
样例输出
Case 1: 2
Case 2: 2
Case 3: 8
Case 4: 12
Case 5: 32
Case 6: 528
解题思路：列出一个时间表
0
1
2
3
4
5
0
2
0
0
0
0
0
1
0
2
0
0
0
0
2
6
0
2
0
0
0
3
4
6
0
2
0
0
4
18+2
4
6
0
2
0
5
12+12
18+2
4
6
0
2
第一行和第一列为时刻，以最后一行为例解释一下这个表的意义。第5时刻试刚出生的(即位于0时刻)的宠物有12+12只，成长了1单位时间的宠物为18+2只，成长了2单位时间的宠物为4只，以此类推。输出的结果为每一行的和。从表中可以发现，每到下一个时刻，上一时刻的宠物数都向后推一格，只要算出新时刻刚出生的宠物数即可。不难发现，f[n][0]=3f[n-1][1]+2f[n-1][2]+f[n-1][3]。这样，所有的问题就都解决了。
代码：
#include<iostream>
using namespace std;
main()
{
intM;
intcount=0;
while((cin>>M)&&(M>=0)&&(M<=2000000000))
{
intsum=0;
intNum[7]={2};
count++;
for(inti=0;i<M;i++)
{
intnum=0;
num=(3*Num[1]+2*Num[2]+Num[3])%10000;
Num[5]=Num[4];
Num[4]=Num[3];
Num[3]=Num[2];
Num[2]=Num[1];
Num[1]=Num[0];
Num[0]=num;
}
for(intj=0;j<6;j++)
sum=sum+Num[j];
cout<<"Case"<<count<<": "<<sum%10000<<endl;
}
}
解题感想：拿到这题第一反应时找到新时刻与上一时刻的关系，用递归解决。就像斐波那契数列那种题目。后来发现找不到新时刻与上一时刻的关系，所以只能换思路了。
