【题解】LA4123[ACM/ICPC World Finals 2008].Glenbow Museum 递推

题目链接
非常巧妙，详见算法竞赛入门经典——训练指南

#include<cstdio>
#include<cstring>
const int maxn=1000;
typedef long long ll;
ll d[maxn+1][5][2],ans[maxn+1];
//d[i][j][k]表示共有i个R，其中有j对相邻的R，第一个元素是k最后一个元素是R，且没有相邻O的序列个数 
int main()
{
    #ifdef local
    freopen("in.txt","r",stdin);
    #endif
    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][1]+d[r][4][0];
    }
    int n,kase=1;
    while(scanf("%d",&n)==1&&n)
    printf("Case %d: %lld\n",kase++,ans[n]);
    return 0;
}