题意

从 个位置中选出两两不相邻而且元素尽可能多的方案数。

分析

我们可以考虑递归有序列 这个时候如果我们在末尾添加了新的元素，那么我们就可以在第 或者第 个选择一个。那么我们就有递推式 。在 时。特判一下就好了。最后输出 因为我们对于最后一个元素可以选择 也可以选择 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 201;
#define LL long long
const int inf = 0x3f3f3f3f;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch=='-')f=1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f?-x:x;
}
LL f[N],num;
int main() {
    f[1]=1;f[2]=1;
    for(int i = 3;i <= 80;i++) f[i]=f[i-2]+f[i-3];
    while(1) {
        int n=read();if(!n)return 0;
        printf("Case #%lld: ",++num);
        if(n==1||n==2)puts("0");
        else if(n==3)puts("1");
        else printf("%lld\n",f[n-1]+f[n]);
    }
}