Jisoo

作为dp来说这个题没啥意思

但是从中我们可以学到数学证明对于dp的指导

例如，只要 $a_j$ 和$a_i$ 都不等于 $0$ 那么这个序列是对数增长

这样似乎暴力也不怎么暴力了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map> 
using namespace std;
map<int,int> ma;
int s[100005];
int a[100005];
int ans;
int n;
int main(){
//  ios::sync_with_stdio(false);
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        ma[a[i]]++;
    }       
    ans=max(ans,ma[0]);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if((!a[i])&&(!a[j])) continue;
            if(i==j) continue;
            int f1=a[i];
            int f2=a[j];
            int tem=2;
            s[1]=a[i];
            s[2]=a[j];
            ma[a[i]]--;ma[a[j]]--;
            while(ma[f1+f2]>0){
                ma[f1+f2]--;
                s[++tem]=f1+f2;
                int temm=f1+f2;
                f1=f2;
                f2=temm;
            } 
        //  cout<<tem<<endl;
            ans=max(ans,tem);
            for(int i=1;i<=tem;++i){
                ma[s[i]]++;
            }
        } 
    }
    cout<<ans; 
    return 0;
}