CF633D Fibonacci-ish 题解

海洋 · 2019-08-20 14:19:59 · 题解

洛谷博客复兴后的第一篇题解。

题意

小y最近迷上了fibonacci数列，他定义了一种数列叫fibonacccccci数列：

1、这个数列包含至少2个元素；

2、f[0]和f[1]是任意选取的；

3、f[n+2]=f[n+1]+f[n] (n>=0)；

现在，给出一个数列a[1..n]，你可以改变数列元素的顺序，使得a[1..m]满足fibonacccccci数列的条件，请求出最大的m。

搞一个桶，计数即可。

#include<bits/stdc++.h>

using namespace std;

const int N=510;

int a[N], f[N], n, ans, now;
map<int, int>m;

int main() {
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]), ++m[a[i]];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(i!=j) {
                if((!a[i])&&(!a[j])) {if(m[0]>ans) ans=m[0];continue;}
                int f1=a[i], f2=a[j]; f[1]=f1,f[2]=f2, now=2, m[f1]--, m[f2]--;
                int w; while(m[w=(f1+f2)]>0) {m[w]--; f[++now]=w; f1=f2; f2=w;}
                if(now>ans)ans=now; for(int i=1; i<=now; i++)m[f[i]]++;
            }
    printf("%d", ans);
}