题解 | #布置会场(I)#

状态表示：
（1）集合：$f[i][[j]f[i][[j]$ 表示摆好前 $ii$ 个椅子且第 $ii$ 个椅子是 $jj$ 类型的椅子。其中 $j=0j=0$ 表示第 $ii$ 个放 $AA$ 类椅子，$j=1j=1$ 表示第 $ii$ 个放 $BB$ 类椅子。
（2）属性：数量

状态计算：
$j=0\mathrm{：}f[i][0]=f[i-1][0]+f[i-1][1];j\; =\; 0：f[i][0]\; =\; f[i\; -\; 1][0]\; +\; f[i\; -\; 1][1];$
$j=1\mathrm{：}f[i][1]=f[i-2][0]+f[i-2][1];j\; =\; 1：f[i][1]\; =\; f[i\; -\; 2][0]\; +\; f[i\; -\; 2][1];$

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 35;

int n;
int f[N][2];

void init()
{
    f[1][0] = 1, f[2][0] = 1, f[2][1] = 1;
    for (int i = 3; i < N; i ++ )
    {
        f[i][0] = f[i - 1][0] + f[i - 1][1];
        f[i][1] = f[i - 2][0] + f[i - 2][1];
    }
}

int main()
{
    init();
    
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> n;
        cout << f[n][0] + f[n][1] << endl;
    }
    
    return 0;
}