思路：观察到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#include #include #include 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; }