首先我们按照这三个U的位置来分类，当前三个U在i，i+1, i+2。

那么先看三个U前面，前面不能有三个U，因为我们不能重复计算

那么就是所有的组合减去有U的情况

为了叙述方便，我们设答案为f（n），没有三个U的方案数为 g（n）

那么显然g（n） = 2的n次方-f（n）

然后我们看三个U后面，后面就任意了是2的（n-i-2）次方

但是这里有一个问题，就是可能第i-1个可以和i，i+1组成三个U

或者i-2与i-1，i组成三个U

那么我们就强行让第i-1个是L，就可以避免这种情况

当i-1不存在，即i=1的时候，这个时候需要特判一下

这个时候第1,2,3个为U，后面随便组，答案是2的（n-3）次方

#include
    
     #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std;const int MAXN = 31;int f[MAXN], g[MAXN];int main(){	f[0] = f[1] = f[2] = 0;	g[0] = 1; g[1] = 2; g[2] = 4;	REP(n, 3, MAXN)	{		f[n] = 1 << (n - 3);		REP(i, 2, n - 1)			f[n] += g[i-2] << (n - i - 2);		g[n] = (1 << n) - f[n];	}		int n;	while(~scanf("%d", &n) && n)		printf("%d\n", f[n]);		return 0;}