A Za, A Za, Fighting...

坚信:勤能补拙

PKU 2663 Tri Tiling

问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2663

思路:
参考: http://www.tkz.org.ru/2009-07/poj-2663-tri-tiling/

递推题。经典。

本题是POJ2506 Tiling的威力加强版。由两行变成了三行。

推导过程与POJ2506异曲同工。

opt[i]=3*opt[i-2]+2*opt[i-4]+2*opt[i-6]+2*opt[i-8]+……直到方括号内表达式的值为0。

解释一下,3*opt[i-2]是最右边有三行2列的三种情况。

后面的2*opt[i-X],则是最右边有X列类似以下的结构的情况:

X=4列的情况:2663_1.jpg;X=6列的情况2663_2.JPG;等等等等

以上情况可以上下颠倒,故每种情况又有两种表示,所以需要乘以2。而以上的情况从4开始,然后每次递增2,所以递推式中这部分从i-4开始(如果大等于0的话),每次递减2。

如果i为奇数,稍微推一下,可得,奇数的列数无解,答案为0。

代码:

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #define MAX_LEN 31
 5 long table[MAX_LEN];
 6 
 7 void
 8 build_table()
 9 {
10     int i, j, sum;
11     memset(table, 0sizeof(table));
12     table[0= 1;
13     table[2= 3;
14     for(i=4; i<MAX_LEN; i=i+2) {
15         sum = 3*table[i-2];
16         for(j=4; i-j>=0; j=j+2)
17             sum += (table[i-j]<<1);
18         table[i] = sum;
19     }
20 }
21 
22 int
23 main(int argc, char **argv)
24 {
25     int n;
26     build_table();
27     while(scanf("%d"&n)!=EOF && n!=-1) {
28         printf("%ld\n", table[n]);
29     }
30 }

posted on 2010-08-16 10:44 simplyzhao 阅读(270) 评论(0)  编辑 收藏 引用 所属分类: G_其他


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


导航

<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜