第9回ブルーブリッジカップ(国試合)——レーザースタイル

【問題の説明】
x星の盛大な祝日は雰囲気を高めるために、30台の机光器で一列に並び、宇宙に光柱を打ち出す.デバッグをインストールしたところ、なぜか隣接する2台のレーザが同時に開かないことがわかりました!王は、このようなバグが存在する場合、全部で何種類のレーザー効果を出すことができるか知りたいと思っています.明らかに、3台の機械しかなければ、全部で5つのスタイルになることができます.1、全部閉めます(sorry、この時は音がなくて音がします.これも1つです).2、1台開けます.3種類3、2台開けます.1種類だけですが、30台はよくありません.王はあなたに手伝ってもらうしかありません.
【答えの提出】30台のレーザで形成できるパターン種数を示す整数を提出することが要求される.整数は1つだけ提出し、余分な内容を記入しないでください.
答え:2178309
暴力&ビット演算を解く:プログラムは20 s実行する

#include 
using namespace std;

inline int judge(int x, int k)                     //    inline   ，    50s 
{
	return x >> k & 1;                             //    x          k      1
}

int main()
{
	int ans = 0;
	for (int i = 0; i < 1 << 30; i ++)
	{
		bool flag = true;
		for (int j = 1; j < 30; j ++)
			if(judge(i, j) && judge(i, j - 1))
			{
				flag = false;
				break;
			}
		ans += flag;	
	}
	
	cout << ans << endl;
	return 0;
} 

問題解2 DFS:

#include 
using namespace std;

int ans;
const int N = 30;
bool st[N];

void dfs(int u)
{
    if(u == 30)
    {
        ans ++;
        return;
    }
                          //            
                          
    dfs(u + 1);              // 1、  
    
    if(!st[u - 1])           // 2、  
    {
        st[u] = true;
        dfs(u + 1);
        st[u] = false;
    }
}

int main()
{
    dfs(0);
    cout << ans << endl;
    return 0;
}

3つの動的計画を解く:

#include 
using namespace std;

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