x星球的盛大节日为增加气氛，用30台机光器一字排开，向太空中打出光柱。 安装调试的时候才发现，不知什么原因，相邻的两台激光器不能同时打开！ 国王很想知道，在目前这种bug存在的情况下，一共能打出多少种激光效果？
显然，如果只有3台机器，一共可以成5种样式，即： 全都关上（sorry, 此时无声胜有声，这也算一种） 开一台，共3种 开两台，只1种
30台就不好算了，国王只好请你帮忙了。
要求提交一个整数，表示30台激光器能形成的样式种数。
注意，只提交一个整数，不要填写任何多余的内容。
思路，从第一盏灯开始开，每个灯能否开启，只取决于前一盏灯的状态
#include<iostream> using namespace std; bool a[31]={false}; //开始状态设为所有灯未点亮 long long cut=0; //记录可以有多少种点法 void dfs(int x){ //设置第X盏灯的开关 if(x>30){ //如果X大于30 ，则获得了一种灯开关的排列方式 cut++; return ; } dfs(x+1); //默认当前灯为关，继续下一盏灯的开关设置 if(a[x-1]==false){ //如果前一盏灯为关闭的，则设置当前为开的，进行下一个尝试 a[x]=true; //开灯 dfs(x+1); a[x]=false; //状态还原 } } int main(){ dfs(1); cout<<cut<<endl; return 0; } //答案 ：2178309
