题目：Click here
题意：bestcoder 上面有中文题目
分析：令f[i]为最后一个木人桩摆放在i位置的方案，令s[i]为f[i]的前缀和。很容易就能想到f[i]=s[i-3]+1,s[i]=s[i-1]+f[i],而s[n]即是所求答案。本题唯一一个值得注意的点就是当n接近60时会爆int。
#include <iostream>
#include <cstdio>
#include <cmath>
typedef long long ll;
using namespace std;
const int M = 1e5+; int n;
ll a[] = { , , , };
int main() {
#ifdef ONLINE_JUDGE
#else
freopen( "in.txt", "r", stdin );
#endif
for( int i=; i<=; i++ ) { //预处理
for( int j=; j<i; j++ ) {
a[i] += a[i-j];
}
a[i] += i;
}
while( ~scanf("%d", &n ) ) {
printf("%I64d\n", a[n] );
}
return ;
}