题意：
这种所有边都是垂直或水平的多边形，可以用一个字符串来表示，一个270°的内角记作O，一个90°的内角记作R。
如果多边形内存在一个点，能看到该多边形所有的点，则这个多边形对应的序列是合法的。这里长度不作限制，只要长度适当能满足要求即可。
现给出序列长度，问有多少种序列符合要求。
分析：
书上分析地很清楚，罗列一下要点：
首先对于一个长度为n的合法序列，R的个数为(n+4)/2，O的个数为(n-4)/2，即R比O多4个
我们要找的序列满足要求：R比O多4个，没有两个O相邻。
这里先设计了一个O(n2)递推的状态，很好理解，看下面那个O(n)的递推
f(i, j, k)表示有i个R，有j对相邻的R，k(k=0表示R，k=1表示O)开头，R结尾的序列个数。
边界：
f(1, 0, 0) = 1,对应串R；f(1, 0, 1) = 1,对应串OR
状态转移方程：
f(i, j, k) = f(i-1, j, k) + f(i-1, j-1, k)，第一个代表在最后面加OR，第二个表示在最后面加R
答案：
f((n+4)/2, 3, 0) + f((n+4)/2, 4, 1) + f((n+4)/2, 4, 0)
第一个表示开头结尾都是R的串，串中有3对相邻的R，因为串是环状的，所以首尾也算一对，共4对R
第二个是O开头，R结尾的串
第三个看起来是R开头结尾，而且中间还有4对R，但只要在最后加上一个O就行了，这样不影响R的个数，对数，总之不影响整个状态的表示。
#include <cstdio> const int maxn = ; long long d[maxn + ][][], ans[maxn + ]; void Init()
{
d[][][] = d[][][] = ;
for(int i = ; i <= maxn; i++)
for(int j = ; j < ; j++)
for(int k = ; k < ; k++)
{
d[i][j][k] = d[i-][j][k];
if(j) d[i][j][k] += d[i-][j-][k];
} for(int i = ; i <= maxn; i+= )
{
int R = (i>>) + ;
ans[i] = d[R][][] + d[R][][] + d[R][][];
}
} int main()
{
Init();
int n, kase = ;
while(scanf("%d", &n) == && n) printf("Case %d: %lld\n", kase++, ans[n]);
}
代码君