BNU 4064 条形码设计

题目链接~~>

做题感悟：比赛时一看这题就知道不好做，所以果断放弃。

解题思路：这是一个递推的问题。首先，如果没有后面的限制，那么有递推式f[n]=f[n-1]+2*f[n-2]。即，n-1的情况加上一个竖条，或者n-2的情况加上一块2*2的或二块横条。然后考虑这f[n]种里面有多少种是左右对称的，对于n是奇数的情况，这个数就是s[n]=f[n/2]（即中间一块竖条），对于n是偶数的情况，这个数是s[n]=f[n/2]+f[n/2-1]*2（三种情况，中间一块2*2的，中间两块1*2横条，或者什么都没有）。因为f[n]中不对称的图形被计算了两次，即f[n]=2*不对称种数+s[n]。于是最后的结果就是(f[n]+s[n])/2 。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      #define pret(a,b) memset(a,b,sizeof(a))
     
    
   

    

     

    
    

     

      const int  INF = 99999999 ;
     
    
   

    

     

    
    

     

      const int  MX= 205 ;
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int f[30],s[30] ;
     
    
   

    

     

    
    

     

       f[1]=1 ; f[2]=3 ;
     
    
   

    

     

    
    

     

       s[1]=1 ; s[2]=3 ;
     
    
   

    

     

    
    

     
 for(int i=3 ;i<29 ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       f[i]=f[i-1]+2*f[i-2] ;
     
    
   

    

     

    
    

     
 if(i%2)
     
    
   

    

     

    
    

     

       s[i]=f[i/2] ;
     
    
   

    

     

    
    

     
 else   s[i]=f[i/2]+f[(i-2)/2]*2 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int n,q=1 ;
     
    
   

    

     

    
    

     
 while(~scanf("%d",&n)&&n)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 printf("Case %d:%d\n",q++,(f[n]+s[n])/2) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/21087925