PKU 1953-World Cup Noise

問題概要

n桁の二進数の数値のうち，1が2連続しないものの総数を求めよ

解法

フィボナッチ数列に帰着される

実装(C++)

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long lli;
lli memo[50];
lli solve(int x){
	if(x<=0)return 1;
	if(x==1)return 2;
	if(memo[x]>0)return memo[x];
	return memo[x]=solve(x-1)+solve(x-2);
}
int main() {
	int t;
	cin>>t;
	for(int i=0;i<t;i++){
		int n;
		cin>>n;
		cout<<"Scenario #"<<i+1<<":"<<endl;
		cout<<solve(n)<<endl<<endl;
	}
	return 0;
}