BC之The mook jong

Problem Description

ZJiaQ want to become a strong man, so he decided to play the mook jong。ZJiaQ want to put some mook jongs in his backyard. His backyard consist of n bricks that is 1*1,so it is 1*n。ZJiaQ want to put a mook jong in a brick. because of the hands of the mook jong， the distance of two mook jongs should be equal or more than 2 bricks. Now ZJiaQ want to know how many ways can ZJiaQ put mook jongs legally(at least one mook jong).

Input

There ar multiply cases. For each case, there is a single integer n( 1 < = n < = 60)

Output

Print the ways in a single line for each case.

Sample Input

1

2

3

4

5

6

Sample Output

1

2

3

5

8

12

递推搞定。。。

官方解题：

令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。

开始的时候纠结在每个n能放几个，从而分组（1，2,3,4…）结果怎么也找不出规律。

当时A的时候用的也是递推的方式，放下第一个在第一个位置，剩下的只能是在剩下的i-3个位置放（不用关心在这i-3个位置到底放了几个） = a[i-3]；在第二个位置，再在剩下的i-4个位置放 = a[i-4] ，一次类推。

#include<cstdio>

#include<cmath>

#include<stdlib.h>

#include<map>

#include<set>

#include<time.h>

#include<vector>

#include<queue>

#include<string>

#include<string.h>

#include<iostream>

#include<algorithm>

using namespace std;

#define INF 0x3f3f3f3f

#define LL long long

#define rd(a) scanf("%d",&a)

#define rdLL(a) scanf("%I64d",&a)

#define rdd(a,b) scanf("%d%d",&a,&b)

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define MOD 1000000007

#define mem0(a) memset(a,0,sizeof(a))

#define mem1(a) memset(a,1,sizeof(a))

typedef pair<int , int> P;

int main()

{

    LL a[100];

    int n;

    a[1]=1,a[2]=2,a[3]=3;

    LL sum=1,coun=2;

    for(int i = 4;i<61;i++)

      a[i]=sum+i,sum+=a[coun++];

   while( ~rd(n) ){

    printf("%I64d\n",a[n]);

   }

 return 0;

}