第九届蓝桥杯国赛c++B组第二题

今天早起没事干，因为自己省赛的时候的垃圾状态没能打入决赛很不甘心，就随便点开了一道国赛真题看了看，发现确实不难。

2.激光样式
问题描述
x星球的盛大节日为增加气氛，用30台机光器一字排开，向太空中打出光柱。
安装调试的时候才发现，不知什么原因，相邻的两台激光器不能同时打开！
国王很想知道，在目前这种bug存在的情况下，一共能打出多少种激光效果？
显然，如果只有3台机器，一共可以成5种样式，即：
全都关上（sorry, 此时无声胜有声，这也算一种）
开一台，共3种
开两台，只1种
30台就不好算了，国王只好请你帮忙了。
要求提交一个整数，表示30台激光器能形成的样式种数。
注意，只提交一个整数，不要填写任何多余的内容。
答案：2178309

方法一：
思路：用dfs来做。
1.每一个灯都有两条路可走，打开或者不打开。
2.当一个灯不打开的时候直接往下走就可以了。
3.当一个灯打开的时候，前提是：它前面的灯不打开。（因为我们每次计算都是看的前面的灯，所以就保证了所有相邻的灯不同时打开，每个灯都会和它前面的灯比较。）

弄好思路之后就可以写代码啦~
一道dfs模板题~

#include<bits/stdc++.h>

using namespace std;

const int N = 40;
int st[N];

long long ans;

void dfs(int x){
    if(x > 30){
        ans ++;
        return ;
    }
    dfs(x + 1);  //x不打开
    if(!st[x - 1]){
        st[x] = 1; //x打开
        dfs(x + 1);
        st[x] = 0;
    }
}

int main(){
    dfs(1);
    
    printf("%d",ans);
    
    return 0;
}

方法二：
通过观察发现一个灯2，两个灯3，三个灯5，符合斐波那契数列规律。
因此用斐波那契数列来做。

#include<bits/stdc++.h>

using namespace std;

const int N = 40;
int st[N];

long long f[3];


int main(){
    f[1] = 2;
    f[2] = 3;
    for(int i = 2 ; i < 30 ; i ++){
       f[0] = f[1];
       f[1] = f[2];
       f[2] = f[0] + f[1];
    }
    cout << f[2];
    return 0;
}