题目

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 11,so it is 1n。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

题解

显然存在规律
由于相邻的两个需要相邻两格
因此 dp[i] 和 dp[i-3] 存在关系
找规律有 dp[i] = dp[i-1] + dp[i-3] + 1

具体证明画图很容易理解

数据有限,打表

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <bitset>
using namespace std;

const int maxn = 65;
long long dp[] = {0,1,2,3,5,8,12,18,27,40,59,87,128,188,276,405,594,871,1277,1872,2744,4022,5895,8640,12663,18559,27200,39864,58424,85625,125490,183915,269541,395032,578948,848490,1243523,1822472,2670963,3914487,5736960,8407924,12322412,18059373,26467298,38789711,56849085,83316384,122106096,178955182,262271567,384377664,563332847,825604415,1209982080,1773314928,2598919344,3808901425,5582216354,8181135699,11990037125,17572253480,25753389180,37743426306,55315679787};

bool Do() {
    int n;
    if(!(cin >> n))
        return false;
    cout << dp[n]<<endl;
    return true;
}

int main() {
    /*
    for(int i = 4;i < 65;i++) {
        dp[i] = dp[i - 1] + dp[i - 3] + 1;
        cout<<dp[i]<<",";
    }
    */
    while(Do());
    return 0;
}