ブルーブリッジカップ-レーザースタイル(dfs)

x星の盛大な祝日は雰囲気を高めるために、30台の机光器で一列に並び、宇宙に光柱を打ち出す.デバッグをインストールしたところ、なぜか隣接する2台のレーザが同時に開かないことがわかりました!王は、このようなバグが存在する場合、全部で何種類のレーザー効果を出すことができるか知りたいと思っています.
明らかに、3台の機械しかなければ、全部で5種類のスタイルにすることができます.つまり、すべて閉じる(sorry、この時は音がなくて音があって、これも1種類です)1台を開いて、3種類で2台開いて、1種類だけです.
30台はまずいから、王は君に手伝ってもらうしかない.
30台のレーザで形成できるパターン種数を表す整数を提出する必要がある.
整数は1つだけ提出し、余分な内容を記入しないでください.
答え:2178309
最初は30台见てたけど、暴捜とか全列并とか出てこなかったんだろうな.
フィボナの粘り強い数列に似た法則
最初の数から直接結果を求めることができます
後でブログを見て、大物のコードを見てやっと分かった.現在の明かりには2つの状況がある.
1.オフ(前のランプの場合は考慮しない)
2.つける(この場合は前のランプがオフになっていることを保証する必要があります)

#include
using namespace std;
int ans=0;
int vis[55];
void dfs(int count){
	if(count==31){
		ans++;
		return ;
	}
	if(count>=31)
	    return ;
	dfs(count+1);//         
	if(!vis[count-1]){ //         
		vis[count]=1;  //        
		dfs(count+1);
		vis[count]=0;  //   
	}
}
int main(){
	dfs(1);
	cout<