ZJiaQ为了强身健体。决定通过木人桩练习武术。ZJiaQ希望把木人桩摆在自家的那个由1*1的地砖铺成的1*n的院子里。
因为ZJiaQ是个强迫症，所以他要把一个木人桩正好摆在一个地砖上，因为木人桩手比較长。所以两个木人桩之间地砖必须大于等于两个，如今ZJiaQ想知道在至少摆放一个木人桩的情况下，有多少种摆法。
输入有多组数据。每组数据第一行为一个整数n(1 < = n < = 60)
对于每组数据输出一行表示摆放方案数
1 2 3 4 5 6
1 2 3 5 8 12
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;
int num;
long long a[65];
int main()
{
a[1]=1;
a[2]=2;
a[3]=3;
a[4]=5;
a[5]=8;
a[6]=12;
a[7]=18;
a[8]=27;
a[9]=40;
a[10]=59;
a[11]=87;
a[12]=128;
a[13]=188;
a[14]=276;
a[15]=405;
a[16]=594;
a[17]=871;
a[18]=1277;
a[19]=1872;
a[20]=2744;
a[21]=4022;
a[22]=5895;
a[23]=8640;
a[24]=12663;
a[25]=18559;
a[26]=27200;
a[27]=39864;
a[28]=58424;
a[29]=85625;
a[30]=125490;
a[31]=183915;
a[32]=269541;
a[33]=395032;
a[34]=578948;
a[35]=848490;
a[36]=1243523;
a[37]=1822472;
a[38]=2670963;
a[39]=3914487;
a[40]=5736960;
a[41]=8407924;
a[42]=12322412;
a[43]=18059373;
a[44]=26467298;
a[45]=38789711;
a[46]=56849085;
a[47]=83316384;
a[48]=122106096;
a[49]=178955182;
a[50]=262271567;
a[51]=384377664;
a[52]=563332847;
a[53]=825604415;
a[54]=1209982080;
a[55]=a[54]+a[52]+1;
a[56]=a[55]+a[53]+1;
a[57]=a[56]+a[54]+1;
a[58]=a[57]+a[55]+1;
a[59]=a[58]+a[56]+1;
a[60]=a[59]+a[57]+1;
while(cin>>num)
{
cout<<a[num]<<endl;
}
return 0;
}
原文：http://www.cnblogs.com/llguanli/p/6866376.html