做题感悟:比赛时一看这题就知道不好做,所以果断放弃。
解题思路:这是一个递推的问题。首先,如果没有后面的限制,那么有递推式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 ; }