UVa 10918 - Tri Tiling
传送门
题意
有一个3xn的矩形，装2x1的矩形，有多少种方案。
思路
显然，当n为奇数的时候不可能实现。
考虑加入第n列的时候。
如果把第n列和第n-1列孤立出来放矩形，可以放3种（这个不难数，这样$f(n) = 3 * f(n - 2)$
但是加入第n列，n - 3和n - 2列也可以放矩形了（本来不可以
如图所示（七牛挂了，日后再上
所以目前$f(n) = 3 * f(n - 2) + 2 * f(n - 4)$
上面那种情况是把n - 4 ~ n孤立出来的情况。但是n - 4 和n - 5又可以串通。如图
以此类推，一直到n = 0
\[f(n) = 3f(n - 2) + 2f(n - 4) + … + 2f(0)\]取前一项，相减得
\[f(n) = 4f(n - 2) - f(n - 4)\]OEIS上也有
代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
LL dp[35];
int main()
{
int n;
dp[0] = 1, dp[2] = 3;
for (int i = 4; i <= 30; i += 2)
dp[i] = 4 * dp[i - 2] - dp[i - 4];
while (scanf("%d", &n), n >= 0)
printf("%lld\n", dp[n]);
return 0;
}