uva 10918 - Tri Tiling（规律）

题目链接：uva 10918 - Tri Tiling

题目大意：给出n，计算用1*2的瓷砖有多少种方法铺满3*n的地方。

解题思路：和uva 10359 - Tiling有点相似，不过难度会比较大，公式c[i] = 4 * c[i - 2] - c[i - 4].

推导过程：c[0] = 1, c[2] = 3, c[4] = c[2] * 3 + c[1] * 2, c[6] = c[4] * 3 + (c[0] + c[2]) * 2 ....

即c[i] = c[i - 2] * 3 + 2 *∑(0≤j≤-4) c[j], 然后带入前一项的公式可以化简成上面的公式。

#include <stdio.h>#include <string.h>#define ll long longll n, c[35];void init() {memset(c, 0, sizeof(c));c[0] = 1;c[2] = 3;for (int i = 4; i <= 30; i++)c[i] = 4 * c[i - 2] - c[i - 4];}int main() {init();while (scanf("%lld", &n), n!= -1) {printf("%lld\n", c[n]);}return 0;}