题目
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
6Sample 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; }