uva 1073 - Glenbow Museum(递推)

题目链接：1073 - Glenbow Museum

题目大意：一个边平行与坐标轴的多边形，可以通过描述角的方式来表示，R表示90度，O表示270度，现在给出序列的长度L，问可以构造出多少种不同的多边形，要求构造出来的多边形在内部有一点可以看到边界的每一个点（我的理解应该是凸多边形）。

解题思路：首先确定是一个凸多边形，所以不可能有两个O相邻，并且在整个序列中，要有4个的RR（即两个R相连，用于转向），所以R的个数应该比O的个数多4，一个O再一个R等于方向没有变。于是n<4和n为奇数的情况根本就是无解的。于是我们知道R的个数应该是(n+4)/2.
dp[i][j][k]表示i个R，j对RR相连，k表示起始的位置为R还是O，并且以R结尾的方式共同有多少种
ans=dp[t][3][0]+dp[t][4][1]+dp[t][4][0]; t为R应该的个数，三个状态分别为头尾均为R、头为O尾为R、R为头O为尾。

#include <cstdio>
#include <cstring>

typedef long long ll;
const int N = 1005;

ll dp[N][5][2], ans[N];

void init () {
    for (int s = 0; s < 2; s++) {

        dp[1][0][s] = 1;

        for (int i = 2; i < N; i++) {
            for (int j = 0; j <= 4; j++) {
                dp[i][j][s] = dp[i-1][j][s];
                if (j)
                    dp[i][j][s] += dp[i-1][j-1][s];
            }
        }
    }

    memset(ans, 0, sizeof(ans));
    for (int i = 1; i < N; i++) {
        if (i < 4 || (i&1))
            continue;

        int t = (i + 4) / 2;
        ans[i] = dp[t][3][0] + dp[t][4][1] + dp[t][4][0];
    }
}

int main () {
    init ();
    int n, cas = 1;
    while (scanf("%d", &n) == 1 && n) {
        printf("Case %d: %lld\n", cas++, ans[n]);
    }
    return 0;
}