The mook jong

 

 Accepts: 506

 

 Submissions: 1281

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

 

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

问题描写叙述

ZJiaQ为了强身健体。决定通过木人桩练习武术。

ZJiaQ希望把木人桩摆在自家的那个由1*1的地砖铺成的1*n的院子里。

因为ZJiaQ是个强迫症，所以他要把一个木人桩正好摆在一个地砖上，因为木人桩手比較长。所以两个木人桩之间地砖必须大于等于两个，如今ZJiaQ想知道在至少摆放一个木人桩的情况下，有多少种摆法。

输入描写叙述

输入有多组数据。每组数据第一行为一个整数n(1 < = n < = 60)

输出描写叙述

对于每组数据输出一行表示摆放方案数

输入例子

1	23456

输出例子

1235812

这个题目有一个递推关系就是f[n]=f[n-1]+f[n-3]+1

怎么来的呢。就是当1*n-1个格子扩展到1*n的格子时，

当多出来的那一个格子为0时，数量=f[n-1]

当多出来的那一个格子为1时，数量=f[n-3]再加上新来的那个为1的格子，多了一种排法，即f[n-3]+1

事实上一个循环全然能够做，但当时着急对着这个公式写了一个递归，结果到五十几的时候出不来结果 ，太慢了，索性由于输入也不多就直接打表。。。

代码：

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #pragma warning(disable:4996)using namespace std;int num;long long a[65];int main(){ a[1]=1; a[2]=2; a[3]=3; a[4]=5; a[5]=8; a[6]=12; a[7]=18; a[8]=27; a[9]=40; a[10]=59; a[11]=87; a[12]=128; a[13]=188; a[14]=276; a[15]=405; a[16]=594; a[17]=871; a[18]=1277; a[19]=1872; a[20]=2744; a[21]=4022; a[22]=5895; a[23]=8640; a[24]=12663; a[25]=18559; a[26]=27200; a[27]=39864; a[28]=58424; a[29]=85625; a[30]=125490; a[31]=183915; a[32]=269541; a[33]=395032; a[34]=578948; a[35]=848490; a[36]=1243523; a[37]=1822472; a[38]=2670963; a[39]=3914487; a[40]=5736960; a[41]=8407924; a[42]=12322412; a[43]=18059373; a[44]=26467298; a[45]=38789711; a[46]=56849085; a[47]=83316384; a[48]=122106096; a[49]=178955182; a[50]=262271567; a[51]=384377664; a[52]=563332847; a[53]=825604415; a[54]=1209982080; a[55]=a[54]+a[52]+1; a[56]=a[55]+a[53]+1; a[57]=a[56]+a[54]+1; a[58]=a[57]+a[55]+1; a[59]=a[58]+a[56]+1; a[60]=a[59]+a[57]+1; while(cin>>num) { cout<
             
              <