2019独角兽企业重金招聘Python工程师标准>>>

                                  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 2 3 4 5 6

---

Sample Output

1 2 3 5 8 12

 Source

BestCoder Round #50 (div.2)

题意

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

1

2

3

···

···

n

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

☆

☆

☆

☆

☆

☆

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

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

是不是好像发现了什么？

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

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

---

Tips

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

---

#include<iostream> 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<<a[n]<<endl;}return 0; }

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

总结

以上是生活随笔为你收集整理的【HDU 5366】The mook jong 详解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。