【ICPC 2018 Malaysia】UPC-9302 ELI'S CURIOUS MIND(递推)

题目描述
Eli is a teenager who loves to study chemistry. She recently joined a chemistry research lab.
Dr. Phil wants her to just play around with some chemicals and observe their reaction.
Therefore, he gave her a one-row tray of test tubes with the different chemical inside of them and told her:
"Mix these chemical together anyhow that you like, but the you have to follow two rules:

1. Never make a mixture that has two chemicals that their tubes are next to each other.
2. Keep adding more chemical to the mixture until it is not violating the new rule. "
   For example, in the image you can see she was given 5 tubes and she is able to make 4 different mixture without violating the rule: {1,3,5}, {2,4}, {2,5}, {1,4}.
   But she cannot mix 1 and 3 only because she still can add 5 without violating the rules.
   She is curious to know how many different mixtures she can make without violating the rule with any given number of tubes. That’s why she asks you write a code to calculate it for her.

输入
The input will consist of a sequence of numbers N, 1≤N≤ 76. Each number will be on a separate line. The input will be terminated by 0.

输出
Output the number of different mixture she can make without violating the rule mentioned above on a single line as show in the sample. The number of all subsets will be less than 231 .

样例输入
1
2
3
4
5
30
0

样例输出
Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 3
Case #5: 4
Case #6: 4410

题意： 有编号为1~n的试管，现在规定相邻两个试管不能混合，其余的可以混合，问可以得到多少种不同的混合物，若一种混合方式包含了另一种集合中的所有混合物，即算同一种混合方式。

举例说明：
1个试管：0种混合方式
2个试管：0种混合方式
3个试管：1种混合方式 {1,3}
4个试管：3种混合方式 {1,3}、{2,4}、{1,4}
5个试管：4种混合方式 {1,3,5}、{2,4}、{2,5}、{1,5}
6个试管：5种混合方式 {1,3,5}、{1,3,6}、{2,4,6}、{2,5}、{1,4,6}
…以此类推

可以发现，因为要求不相邻的试管混合，因此每次新添一个试管i，新试管的混合方案总是和第i-2和i-3位置的所有试管混合，不会跨越到i-4是因为i到i-4之间肯定会有一个i-2插在中间，就比如6不会和2再添新组合是因为2,4,6中包含了2,6。
因此每次第i个试管的混合物方式总是i-2与i-3个试管的总和。
又因为，虽然新试管不能和i-1中某些相邻的集合混合。但是其混合方式是存在的，我们直接继承下来，继承下来i-1个试管中没有用到试管i的所有组合方式。
这样一来一个递推就可以得到结果。
最后利用样例或者手推得到的试管1到试管5的结果做递推的初始化。
其中3个试管时就1种没有问题，4个试管时，因为继承了4-1=3的集合{1,3}，因此要删掉这个继承值，我们只计数用到新试管的混合方式。因此4个试管时2种。
同理，5个试管时，{1,3,5}继承自{1,3}，不算，{2,4}没有用到新试管，不算，真正新生成的混合方式只有{1,5}和{2,5}，因此5个试管时是2.
在后续增加更多的试管时，就不会出现这样的凭空增加了，因为最后全部是以{1,3}、{1,5}、{2,4}、{2,5}所生成的新序列，因为之前说的，只考虑i-2和i-3的增加，小于i-4的位置都会夹着i-3或i-2.
代码如下：

#include<bits/stdc++.h>
#define LL long long
#define M(a,b) memset(a,b,sizeof a)
#define pb(x) push_back(x)
using namespace std;
const int maxn=1e3+7;
int n;
LL a[80];
int main()
{
    int cas=1;
    a[1]=a[2]=0;
    a[3]=1,a[4]=a[5]=2;
    for(int i=6;i<=76;i++)a[i]=a[i-2]+a[i-3];
    while(scanf("%d",&n)&&n) printf("Case #%d: %lld\n",cas++,a[n-1]+a[n]);
}