首页 > 代码库 > （dp）hihocoder - 1239 Fibonacci
（dp）hihocoder - 1239 Fibonacci
原题链接：http://hihocoder.com/problemset/problem/1239
题意：给一个数列，求构成斐波那契数列的子序列有几个。
分析：我们可以在统计的过程中动态加出结果。
由于有两个1，我们需要进行一些区分，我们首先定义m[0]表示以第一个1为结尾的斐波那契数列的个数，m[1]表示以第二个1为结尾的斐波那契数列的个数，同理，m[i](i>1，i表示斐波那契数的编号)表示以Fibonacci(i)为结尾的斐波那契数列的个数。
比如这个例子1 1 2 1 2 3 4 5 。
①假设一开始1，这时m[0]=1。
②接着又一个1，这时由于m[0]=1之前已经有一个以第一个1为结尾的数列，所以m[1]+=m[0]，又由于1单独自身能成为一个数列，所以m[0]+=1。
③接下来是2，我们需要看他前面那个斐波那契数，也就是第二个1，所以m[2]+=m[1]。
④然后是又是1，跟②一样，先加上已经有的，然后加上自己新的。m[1]+=m[0]，m[0]+=1。
⑤依然是2，跟③一样，m[2]+=m[1]。
⑥然后是3，跟③⑤类似，m[3]+=m[2]。
⑦这次是4，发现不是斐波那契数，直接跳过。
⑧最后是5，依然类似，m[4]+=m[3]。
代码：
1 #include <set> 2 #include <map> 3 #include <list> 4 #include <cmath> 5 #include <queue> 6 #include <vector> 7 #include <bitset> 8 #include <string> 9 #include <cctype>10 #include <cstdio>11 #include <cstring>12 #include <cstdlib>13 #include <iostream>14 #include <algorithm>15 16 using namespace std;17 18 typedef long long ll;19 typedef unsigned long long ull;20 #define inf (0x3f3f3f3f)21 #define lnf (0x3f3f3f3f3f3f3f3f)22 #define eps (1e-8)23 int sgn(double a) {return a < -eps ? -1 : a < eps ? 0 : 1;}24 25 //--------------------------26 27 28 const ll mod = 1000000007;29 30 int fb[30] = {1, 1, 2};31 ll tb[30];32 map<int, int> m;33 int p;34 int n;35 36 void init() {37 m[1] = 1;38 m[2] = 2;39 for (p = 3;; p++) {40 if (fb[p - 1] + fb[p - 2] > 100000)break;41 fb[p] = fb[p - 1] + fb[p - 2];42 m[fb[p]] = p;43 44 }45 }46 47 48 49 void solve() {50 init();51 while (~scanf("%d", &n)) {52 memset(tb, 0, sizeof(tb));53 ll ans = 0;54 int x;55 int k = 0;56 for (int i = 0; i < n; i++) {57 scanf("%d", &x);58 59 int *lo = lower_bound(fb, fb + p, x);60 if (*lo != x) continue;61 if (x == 1) {62 ans = (ans % mod + tb[0] % mod) % mod;63 tb[1] = (tb[1] % mod + tb[0] % mod) % mod;64 tb[0] = (tb[0] % mod + 1) % mod;65 ans = (ans % mod + 1) % mod;66 } else {67 tb[m[x]] = (tb[m[x]] % mod + tb[m[x] - 1] % mod) % mod;68 ans = (ans % mod + tb[m[x] - 1] % mod) % mod;69 }70 }71 72 printf("%lld\n", ans );73 }74 75 }76 77 int main() {78 79 #ifndef ONLINE_JUDGE80 freopen("1.in", "r", stdin);81 //freopen("1.out", "w", stdout);82 #endif83 //iostream::sync_with_stdio(false);84 solve();85 return 0;86 }
（dp）hihocoder - 1239 Fibonacci
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。