题解

这一道题的递推式推出来不难。首先，在后面加一个数字就只能是奇数或者偶数。那我们设想一下，如果前一位是2，那后一位也得是2。因此，递推数组只需加一即可。而如果前一位是奇数，那么后一位就能取1和3。也就是f[i] = f[i - 1] - 1（剪掉全是2的填法）* 2 + 1(加上全是2的填法)。代码如下：

#include<bits/stdc++.h>
using namespace std;
long long a[105];
int main(){
    int n; cin >> n;
    a[2] = 5;
    for(int i = 3;i <= n;i ++){
        a[i] = (a[i - 1] - 1) * 2 + 1; //递推式
    }
    cout << a[n];
    return 0;
}