The mook jong

Accepts: 506

Submissions: 1281

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

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

1235812 题意：问题可以转化成在一个数轴上，隔不低于两个点放至少一个木桩的方法。那么放或是不放点就在那里，你有几种方法放置木桩？（木桩数量不限

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 #include 
            
              7 #include 
             
               8 #include 
              
                9 #include 
               
                10 11 using namespace std;12 13 #define INF 0xfffffff14 #define maxn 1000515 16 int main()17 {18 __int64 n, dp[maxn] = { 1, 2, 3, 5};19 20 while(scanf("%I64d", &n) != EOF)21 {22 for(int i = 3; i <= n; i++)23 dp[i] = dp[i-3] + dp[i-1];24 printf("%I64d\n", dp[n]-1); // 减去一种什么都不放的情况25 26 }27 return 0;28 }