校ACM队准备筹划向学校批请一个专用机房。但是为了防止它变成公用机房，FL建议采用刷卡进入的办法，她设计了一种条形码，每人都对应一个。这种大小为2*n的条形码由以下三种元素构成：1*2、2*1、2*2的长方形方格。但是我们同样也知道，很多人都容易在刷卡时把卡的位置搞反。为了避免机器错误的处理，我们认为下图的两种条形码是一样的（图中颜色只是为方便说明，不用考虑）。
FL现在很想知道一个问题，就是用她的这种条形码编码方式，对于一个给定的长度n最多能有多少不同的条形码可供使用？
多组测试数据，每一行一个正整数n（n≤28），以n = 0时作为结束。
最与每一组数据，先输出“Case k:”，其中k代表case数，接下来输出一个数，可用的的条形码数目m（m不超过231.）
1 2 3 4 5 0
Case 1:1 Case 2:3 Case 3:3 Case 4:8 Case 5:12
注意输出英文字母的大小写也必须正确。
#include<cstdio>
int main()
{
int i, n, cas = 0;
int a[30] = {0, 1, 3}, b[30] = {0, 1, 3};
for(i = 3; i <= 28; i++)
{
a[i] = a[i-1] + 2 * a[i-2];
if(i & 1)
b[i] = a[(i-1)/2];
else
b[i] = a[i/2] + 2 * a[(i-2)/2];
}
while(~scanf("%d",&n) && n)
{
printf("Case %d:%d\n",++cas, (a[n]+b[n])/2);
}
return 0;
}BNUOJ 4064 条形码设计 (动态规划 + 递推）,布布扣,bubuko.com
原文：http://blog.csdn.net/lyhvoyage/article/details/21152675