学步园

UVA_11069

    这个题目要求求出原图的最大独立点集的个数。

    我们不妨考虑一下第1个点的选择与否来看看能不能得到一些递推关系。如果选第1个点的话，那么一定不能选第2个点，但是否一定选第3个点呢？不一定，因为也可以选第4个点。实际上第2个点后面只要是n-2个点的最大独立点集就可以，因为里面必然有一个3或者4。这样f(n)最起码有一部分的数值等于f(n-2)。

    接下来考虑不选第1个点的情况，那么就必然要选第2个点，必然不选第3个点，第3个点以后的选择情况就和上面一样了，只要是n-3个点的最大独立点集就可以，这样我们就得到总的递推公式了，f(n)=f(n-2)+f(n-3)。

#include<stdio.h>
#include<string.h>
#define MAXD 80
int f[MAXD];
void prepare()
{
int i;
    f[1] = 1, f[2] = 2, f[3] = 2;
for(i = 4; i <= 76; i ++)
        f[i] = f[i - 2] + f[i - 3];
}
int main()
{
int n;
    prepare();
while(scanf("%d", &n) == 1)
        printf("%d\n", f[n]);
return 0;
}