fzu 1533

Problem 1533 Subset

Accept: 299    Submit: 740
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

整数集合Sn={1,2,...,n}的非空子集如果不含两个相邻的自然数，则称为好子集。你的任务是求好子集的个数。

Input

有多组测试数据。每个测试数据一行,有一个正整数，表示n(1≤n≤70)。

Output

对于每组测试数据，输出一个数表示Sn的好子集的个数

Sample Input

3

Sample Output

4

Hint

{1},{2},{3},{1,3}.

Source

FOJ月赛-2007年9月

开头用dp， 从后往前推理

dp(i) 为以第i项作为结尾的好子集个数

第i项可以选，也可以不选。

选的情况下因为不相邻的限制，就递归dp(i-2)。  不选递归dp(i-1)

dp(i)=dp(i-2)+dp(i-1)

最终结果要减一，因为算出来的包含空集

后面知道这是fibonacci ,就直接计算了。

#include <cstdio>

#include <cmath>

#include <string.h>

#include <iostream>

using namespace std;

const int maxn=70+5;

typedef long long LL;

LL d[maxn];

LL dp(int n)//包含空集情况

{

    if(n==1)// {}, {1}

    {

        return 2;

    }

    else if(n==2)// {}, {1}, {2}

    {

        return 3;

    }

    LL &ans = d[n];

    if(ans>0)

        return ans;

    // 每层都可以选或不选

    ans = dp(n-1) + dp(n-2);

    return ans;

}

long long fib[maxn]={1, 2, 3};

void fibonacci(int n)

{

    for(int i=3;i<=n;i++)

    {

        fib[i] = fib[i-1] + fib[i-2];

//        cout<<fib[i]<<endl;

    }

}

int main()

{

    int n;

    fibonacci(70);

    while(scanf("%d", &n)==1)

    {

        //        printf("%lld", dp(n)-1);//减去一个空集 fzu坑，不能用lld 要用 I64d

//        cout << dp(n)-1 << endl;

        cout << fib[n]-1 << endl;

    }

    return 0;

}

关于fibonacci参考链接：

http://courseware.eduwest.com/courseware/0350/content/zhonghe/tc11.html