Fibonacci

Fibonacci

Description:

Given a sequence {an}, how many non-empty sub-sequence of it is a prefix of fibonacci sequence.

A sub-sequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

The fibonacci sequence is defined as below:

F1 = 1, F2 = 1

Fn = Fn-1 + Fn-2, n>=3

Input:

One line with an integer n.

Second line with n integers, indicating the sequence {an}.

For 30% of the data, n<=10.

For 60% of the data, n<=1000.

For 100% of the data, n<=1000000, 0<=ai<=100000.

Output:

One line with an integer, indicating the answer modulo 1,000,000,007.

Tips:

The 7 sub-sequences are:

{a2}

{a3}

{a2, a3}

{a2, a3, a4}

{a2, a3, a5}

{a2, a3, a4, a6}

{a2, a3, a5, a6}

Sample input:

6
2 1 1 2 2 3

Sample output:

7

分析：

   如果用深搜，复杂度是O(2n)，所以会超时，可以用DP优化。

Code:

DP：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdlib.h>
#include <stdio.h>
#include<algorithm>
#include <vector>

using namespace std;

//http://hihocoder.com/contest/hiho113/problem/1

long long dp[100], m, n, a[1000009], f[100], ans = 0;

int main() {
    f[1] = 1;
    f[2] = 1;
    m = 2;

    while (f[m] < 100000) {
        f[m + 1] = f[m] + f[m - 1];
        m++;
    }

    scanf("%lld", &n);
    for (int i = 0; i < n; i++) scanf("%lld", &a[i]);

    for (int i = 0; i < n; i++) {
        int it = lower_bound(f + 1, f + m + 1, a[i]) - f;
        if (it >= 3 && it <= m && f[it] == a[i]) {
            dp[it] += dp[it - 1];
            ans += dp[it - 1];

            dp[it] %= 1000000007;
            ans %= 1000000007;
        }
        else if (1 == a[i]) {
            dp[2] += dp[1];
            dp[1]++;
            ans += dp[1];
        }
    }
    printf("%lld\n", ans);

    return 0;
}

DFS：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdlib.h>
#include <stdio.h>
#include <vector>

using namespace std;

//http://hihocoder.com/contest/hiho113/problem/1

void dfs(vector<int> &dt, int n, vector<int> rs, int &totalCount) {
    if (n == dt.size() && !rs.empty()) {
        totalCount++;
        return;
    }

    if (n < dt.size()) {
        int m = rs.size();

        dfs(dt, n + 1, rs, totalCount);

        if (m > 1) {
            if (dt[n] == rs[m - 2] + rs[m - 1]) {
                rs.push_back(dt[n]);
                dfs(dt, n + 1, rs, totalCount);
                rs.pop_back();
            }
        }
        else {
            if (dt[n] == 1) {
                rs.push_back(dt[n]);
                dfs(dt, n + 1, rs, totalCount);
                rs.pop_back();
            }
        }
    }
}

int main() {
    vector<int> rs;
    vector<int> dt;
    int n;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        int tem;
        scanf("%d", &tem);
        dt.push_back(tem);
    }

    int totalCount = 0;
    dfs(dt, 0, rs, totalCount);
    printf("%d\n", totalCount);

    system("pause");
    return 0;
}