UVALive - 4123 Glenbow Museum

思路：观察到R的个数比O多4个，且序列中不可能出现OO，且会有四个RR，然后两个相邻的RR边之间有序列“OROROR....RORO”,一共会有(n+4)/2个R和(n-4)/2个O，根据R比O 多4个可以推出

设：d(i,j,k)表示有i个R其中有j对相邻的R，第一个元素是k，答案是：

d{(n+4)/2,3}+d{(n+4)/2,4,0}+d{(n+4)/2,4,1},且 d(i,j,k)=d(i-1,j-1,k)+d(i-1,j,k)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1005;

long long d[MAXN][5][2],ans[MAXN];

int main(){
    memset(d,0,sizeof(d));
    for (int k = 0; k < 2; k++){
        d[1][0][k] = 1;
        for (int i = 2; i <= MAXN; i++)
            for (int j = 0; j < 5; j++){
                d[i][j][k] = d[i-1][j][k];
                if (j > 0)
                    d[i][j][k] += d[i-1][j-1][k];
            }
    }

    memset(ans,0,sizeof(ans));
    for (int i = 1; i <= MAXN; i++){
        if (i < 4 || i%2  == 1)
            continue;
        int r = (i+4)/2;
        ans[i] = d[r][3][0] + d[r][4][0] + d[r][4][1];
    }
    int n,cas=1;
    while (scanf("%d",&n) != EOF && n)
        printf("Case %d: %lld\n",cas++,ans[n]);
    return 0;
}