马尔扎哈的疑惑
时间限制(普通/Java): 1000 MS/3000 MS 运行内存限制 : 65536 KByte总提交 : 247测试通过 : 76
题目描述
众所周知，虚空先知马尔扎哈的被动技能可以召唤宠物用来辅助战斗，但可惜的是，宠物数量最多只能有3个，显然，这不够强力。
最近，通过马尔扎哈的不懈努力，终于改进了这个技能——他第1秒时只有一个宠物，该宠物每过一秒又可以生出一个新宠物，而新宠物从他出生的第3秒开始，每过一秒也可以生出一个新宠物，新的宠物也以此类推。
请问，在第n秒时，马尔扎哈总共有多少个宠物？
输入
先输入一个正整数T，表示样例个数，1≤T≤100；
对于每一个测试样例，输入一个正整数n，表示第n秒，1≤n≤55。
输出
对于每一个测试样例，输出第n秒时，马尔扎哈拥有的宠物数。
题目保证结果在int范围内。
样例输入
2
4
5
样例输出
4
6
跟做的一道求第N年树木枝干的数目有些相似。
#include <cstdio>int a[56];int main(){int n;scanf("%d", &n);int x;a[1] = 1;a[2] = 2;a[3] = 3;for(int i = 4; i <= 61; i++)a[i] = a[i - 1] + a[i - 3];while(n--){scanf("%d", &x);printf("%d\n",a[x]);}}
起初第一次做这样的，不知道优化题解，这是参考田神的做法。
