The mook jong

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 767 Accepted Submission(s): 522

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	23456

Sample Output

Source

题意

大致模型就是说，有一个1*N的格子，（就像下面这样），往里面塞东西，但是每两个之间距离大于等于2.

···

对于样例，输入4有如下5种解法

☆

通过自己举几个例子发现当输入从1~60的时候

输出是这样的 1 2 3 5 8 12······

是不是好像发现了什么？

再结合每两个元素之间至少要2个间距，仔细思考之后得出公式

a[i]=a[i-1]+a[i-3]+1;

Tips

当N接近60的时候数据会很大，注意数据的存储类型！

#include
    
     using namespace std;long long a[61]={0,1,2,3};int main(){    int n;    for(int i=4;i<=60;i++)    {            a[i]=a[i-1]+a[i-3]+1;    }    while(cin>>n){    cout<
     
      <

转载于:https://my.oschina.net/zmixed/blog/625406

你可能感兴趣的文章