题意：ZJiaQ希望把木人桩摆在自家的那个由1*1的地砖铺成的1*n的院子里。由于ZJiaQ是个强迫症，所以他要把一个木人桩正好摆在一个地砖上，由于木人桩手比较长，所以两个木人桩之间地砖必须大于等于两个，现在ZJiaQ想知道在至少摆放一个木人桩的情况下，有多少种摆法。
思路：题意类似于“要求找到所有满足这样要求的二进制的数：（1）不能出现101 （2）不能出现11 （3）不能为0”。
问题是可以降低规模的，也就是也可以递推，假设cnt[i][0]表示第i位放0的所有可能数，cnt[i][1]表示第i位放1的所有可能数，递推式如下：
（1）cnt[i][0]=cnt[i-1][0]+cnt[i-1][1];
（2）cnt[i][1]=cnt[i-2][0]+1;
而答案就是cnt[n][0]+cnt[n][1]。
//#include <bits/stdc++.h>
#include <cstdio>
#include <vector>
#include <deque>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x7f7f7f7f
#define pii pair<int,int>
#define LL long long
using namespace std;
const int N=;
LL cnt[N][];
LL ans[N]; void pre_cal()
{
memset(cnt, , sizeof(cnt));
cnt[][]=;
cnt[][]=; cnt[][]=;
cnt[][]=; ans[]=;
ans[]=; for(int i=; i<N; i++)
{
cnt[i][]=cnt[i-][]+cnt[i-][];
cnt[i][]=cnt[i-][]+;
ans[i]=cnt[i][]+cnt[i][];
}
} int main()
{
freopen("input.txt", "r", stdin);
pre_cal();
int n;
while(cin>>n)
{
cout<<ans[n]<<endl;
}
return ;
}
AC代码
另一种方法是，穷举一下所有可能，打出60个答案，直接用数组保存，速度杠杠的。