Counter Attack
时间限制(普通/Java):1000MS/2000MS 运行内存限制:65536KByte
总提交:404 测试通过:61
总提交:404 测试通过:61
描述
逆袭(Counter Attack)什么的，是必须的，不逆袭，不算活过。DS为逆袭，求教神预言家Master Yu。预言家一听是DS想逆袭，心中一叹曰“喜闻乐见”，随即铺开一列塔罗牌，对DS说：你可以从这列塔罗牌中取走任意多个，但是，不能取走相邻的牌，因为相邻的牌是相刑的，会带来一生孤独运。预言家说完，抬手转身出门而去，远处传来上帝的声音：“若你能找出所有的可行取法，百日内必可被逆推！”
请问，到底有多少种可行的取法呢？
输入
第一行包含一个正整数T (1≤T≤10)，表示有T组测试用例。
每组用例包含一行，仅一个正整数n (1≤n≤50)，表示这列塔罗牌有n张。
输出
每组用例输出一行，仅包含一个整数，即满足规则的可行取法数。
样例输入
1
5
样例输出
13
分析:
F[N]表示N张的取法数,分两种情况:
1.取第N张,那么第N-1张不能取,前N-2张随意取,F[N]+=F[N-2];
2.不取第N张,那么前N-1张随意取,F[N]+=F[N-1];
如下图:
得到动态规划方程:
F[N]=F[N-1]+F[N-2];
注意事项
范围超过int,要用64位整数.
AC代码
#include<iostream>
using namespace std;
int main()
{
int N,n;
long long A[52];
A[1]=2;A[2]=3;
for (int i=3;i<=50;i++)
{
A[i]=A[i-1]+A[i-2];
}
cin>>N;
while (N--)
{
cin>>n;
cout<<A[n]<<endl;
}
return 0;
}
注意事项:范围超过int,要用64位整数.