学步园

 Tri Tiling

这道题总体看来并不算难，刚开始看时打算找规律，没找到，看Discuss里有人给出一公式，也没看明白，又看看别的，也没有明确思路，有人似乎用dp做。

但从公式上看，有了点想法，就是利用之前求出的求后面的，但有些细节很麻烦。

首先只有是偶数才非零，只看偶数就可以了。来一个数n，它比上一个数差2，而2能摆出三种情况，这样如果这个2和前面是分开的，这种情况是 f[n-2] * 3，剩下就要考虑不分开的情况，这也是关键。

仔细分析图可以看出每偶数个格都可以摆成不可分割的，这种情况必须是上下有一排全是横放的，也就是只有两种摆法，这样就很容易了，具体见代码。

#include <iostream><br /> #include <cstring><br /> #include <cmath><br /> #include <cstdlib><br /> #include <algorithm><br /> #include <string><br /> #include <cstdio><br /> #include <climits><br /> using namespace std;<br /> int f[32];<br /> int main()<br /> {<br /> f[0] = 1;<br /> f[2] = 3;<br /> int n;<br /> for (int i=4; i < 32; i++)<br /> {<br /> f[i] = 3 * f[i-2];<br /> int t = i;<br /> while (t >= 4)<br /> {<br /> f[i] += f[i-t] * 2;<br /> t -= 2;<br /> }<br /> }</p> <p> while (cin >> n, n != -1)<br /> {<br /> if (n % 2 == 1)<br /> cout << "0/n";<br /> else<br /> cout << f[n] << endl;<br /> }<br /> return 0;<br /> }<br />

也许化简出来也能出个公式吧，我就不化了。