ZJiaQ为了强身健体，决定通过木人桩练习武术。ZJiaQ希望把木人桩摆在自家的那个由1*1的地砖铺成的1*n的院子里。由于ZJiaQ是个强迫症，所以他要把一个木人桩正好摆在一个地砖上，由于木人桩手比较长，所以两个木人桩之间地砖必须大于等于两个，现在ZJiaQ想知道在至少摆放一个木人桩的情况下，有多少种摆法。
输入有多组数据，每组数据第一行为一个整数n(1 < = n < = 60)
对于每组数据输出一行表示摆放方案数
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 using namespace std; 7 typedef long long LL; 8 const int MS = 62; 9 10 //令f[i]为最后一个木人桩摆放在i位置的方案，令s[i]为f[i]的前缀和。 11 //很容易就能想到f[i]=s[i-3]+1,s[i]=s[i-1]+f[i],而s[n]即是所求答案。 12 //本题唯一一个值得注意的点就是当n接近60时会爆int。 13 14 LL f[MS]; 15 LL s[MS]; 16 17 int main() 18 { 19 int n; 20 memset(f,0,sizeof(f)); 21 memset(s,0,sizeof(s)); 22 f[1] = 1; 23 f[2] = 1; 24 s[1] = 1; 25 s[2] = 2; 26 for(int i = 3;i<MS;i++) 27 { 28 f[i] = s[i-3] + 1; 29 s[i] = s[i - 1] + f[i]; 30 } 31 while(scanf("%d",&n)!=EOF) 32 { 33 printf("%d\n",s[n]); 34 } 35 return 0; 36 }
原文：http://www.cnblogs.com/hutaishi/p/4713979.html