问题:
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列的情况：
；X=6列的情况
；等等等等
以上情况可以上下颠倒，故每种情况又有两种表示，所以需要乘以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, 0, sizeof(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 }