問(wèn)題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2663思路:
參考:
http://www.tkz.org.ru/2009-07/poj-2663-tri-tiling/遞推題。經(jīng)典。
本題是POJ2506 Tiling的威力加強(qiáng)版。由兩行變成了三行。
推導(dǎo)過(guò)程與POJ2506異曲同工。
opt[i]=3*opt[i-2]+2*opt[i-4]+2*opt[i-6]+2*opt[i-8]+……直到方括號(hào)內(nèi)表達(dá)式的值為0。
解釋一下，3*opt[i-2]是最右邊有三行2列的三種情況。
后面的2*opt[i-X]，則是最右邊有X列類似以下的結(jié)構(gòu)的情況：
X=4列的情況：
；X=6列的情況
；等等等等
以上情況可以上下顛倒，故每種情況又有兩種表示，所以需要乘以2。而以上的情況從4開(kāi)始，然后每次遞增2，所以遞推式中這部分從i-4開(kāi)始（如果大等于0的話），每次遞減2。
如果i為奇數(shù)，稍微推一下，可得，奇數(shù)的列數(shù)無(wú)解，答案為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 }