题目：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。

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 typedef long long ll; 5 using namespace std; 6 const int M = 1e5+5; 7  8 int n; 9 ll a[65] = { 0, 1, 2, 3};10 int main()  {11     #ifdef ONLINE_JUDGE12     #else13         freopen( "in.txt", "r", stdin );14     #endif15     for( int i=4; i<=60; i++ )  {   //预处理16         for( int j=3; j