bnu条形码设计（递推）

题目链接：bnu4064

/*
    首先不考虑对称，递推公式：f[n] = f[n-1] + 2*f[n-2];
即n-1的情况加上一个竖条，n-2的情况加上一个2*2的或两个横条
    接着考虑有多种是对称的，n为奇数时：s[n] = f[n/2];  n为偶数时：s[n] = f[n/2] + f[n/2-1]*2;
即（中间是一块2*2的，或两个横条，或没有）；
    f[n] = 2*不对称的种数+s[n];
*/
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; int f[30] = {0,1,3}; int s[30] = {0,1,3}; int main() { int n,i,j; for(i = 3; i <= 28; i ++) { f[i] = f[i-1] + 2*f[i-2]; if(i&1) s[i] = f[i/2]; else s[i] = f[i/2] + f[i/2-1]*2; } int p = 1; while(scanf("%d",&n),n) { printf("Case %d:%d\n",p++,(f[n]+s[n])/2); } return 0; }