NC21339. 斐波那契序列
描述
输入描述
第一行输入一个整数n (1 ≤ n ≤ 50)
第二行输入n个整数表示S集合
数据范围为 1-10^8，S集合每个数都是不同的
输出描述
输出一个整数
示例1
输入:
5 8 1 20 3 10
输出:
5
说明:
牛牛选择了1 3 8，是 1 1 2 3 5 8 13的子序列示例2
输入:
6 19 47 50 58 77 99
输出:
4
示例3
输入:
1 512
输出:
1
示例4
输入:
8 3 5 7 10 13 15 20 90
输出:
7
说明:
牛牛选择了3 5 7 是 3 2 5 7的子序列示例5
输入:
10 1 2 3 5 8 13 21 34 55 89
输出:
10
C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 588K, 提交时间: 2019-06-17 18:58:37
/*#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#include<bits/stdc++.h>
#define ll long long
#define inf 1000000005
#define mod 1000000007
#define put putchar('\n')
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
#define R(i,a,b) for (int i=(a);i<(b);i++)
#define go(i,t) for (int i=head[t];i;i=Next[i])
#define sqr(x) ((x)*(x))
#define re register
#define mp make_pair
#define fi first
#define se second
#define pa pair<int,int>
#define pb push_back
#define be begin()
#define en end()
#define ret return puts("-1"),0;
#define N 500055
#define int ll
using namespace std;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();}
int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;}
inline void wr(int x){if (x<0) {putchar('-');wr(-x);return;}if(x>=10)wr(x/10);putchar(x%10+'0');}
inline void wrn(int x){wr(x);put;}inline void wri(int x){wr(x);putchar(' ');}
inline void wrn(int x,int y){wri(x);wrn(y);}inline void wrn(int a,int b,int c){wri(a);wrn(b,c);}
int n,m,r[N],l[N],a[N],f[N],ans;
pa b[N];
map<int,int> q;
signed main(){
n=read();
F(i,1,n) a[i]=read();sort(a+1,a+n+1);
b[1]=mp(1,0);b[2]=mp(0,1);
F(i,3,47) b[i]=mp(b[i-1].fi+b[i-2].fi,b[i-1].se+b[i-2].se);
F(i,1,n) q[a[i]]=i;
F(i,1,n){
F(j,i+1,n){
int t=2;
f[1]=a[i];f[2]=a[j];
F(k,3,60){
f[k]=f[k-1]+f[k-2];
if (f[k]>inf) break;
if (q.find(f[k])!=q.en) t++,l[q[f[k]]]=max(l[q[f[k]]],t);
}
r[i]=max(r[i],t);
F(k,3,47){
if ((a[j]-a[i]*b[k].fi)%b[k].se==0){
t=2;
f[1]=a[i];f[2]=(a[j]-a[i]*b[k].fi)/b[k].se;
if (f[2]<0) continue;
F(p,3,60){
f[p]=f[p-1]+f[p-2];
if (f[p]>inf) break;
if (p>k){
if (q.find(f[p])!=q.en){
t++;
int wzp=q[f[p]];
l[wzp]=max(l[wzp],t);
}
}
}
r[i]=max(r[i],t);
}
}
}
}
l[1]=1;l[2]=2;r[n]=1;r[n-1]=2;
F(i,1,n) l[i]=max(l[i],l[i-1]);
D(i,n,1) r[i]=max(r[i+1],r[i]);
F(i,0,n) ans=max(ans,l[i]+r[i+1]);
wrn(ans);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 7ms, 内存消耗: 504K, 提交时间: 2019-02-28 18:45:25
/*#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#include<bits/stdc++.h>
#define ll long long
#define inf 1000000005
#define mod 1000000007
#define put putchar('\n')
#define F(i,a,b) for (int i=(a);i<=(b);i++)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
#define R(i,a,b) for (int i=(a);i<(b);i++)
#define go(i,t) for (int i=head[t];i;i=Next[i])
#define sqr(x) ((x)*(x))
#define re register
#define mp make_pair
#define fi first
#define se second
#define pa pair<int,int>
#define pb push_back
#define be begin()
#define en end()
#define ret return puts("-1"),0;
#define N 500055
#define int ll
using namespace std;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();}
int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;}
inline void wr(int x){if (x<0) {putchar('-');wr(-x);return;}if(x>=10)wr(x/10);putchar(x%10+'0');}
inline void wrn(int x){wr(x);put;}inline void wri(int x){wr(x);putchar(' ');}
inline void wrn(int x,int y){wri(x);wrn(y);}inline void wrn(int a,int b,int c){wri(a);wrn(b,c);}
int n,m,r[N],l[N],a[N],f[N],ans;
pa b[N];
map<int,int> q;
signed main(){
n=read();
F(i,1,n) a[i]=read();sort(a+1,a+n+1);
b[1]=mp(1,0);b[2]=mp(0,1);
F(i,3,47) b[i]=mp(b[i-1].fi+b[i-2].fi,b[i-1].se+b[i-2].se);
F(i,1,n) q[a[i]]=i;
F(i,1,n){
F(j,i+1,n){
int t=2;
f[1]=a[i];f[2]=a[j];
F(k,3,60){
f[k]=f[k-1]+f[k-2];
if (f[k]>inf) break;
if (q.find(f[k])!=q.en) t++,l[q[f[k]]]=max(l[q[f[k]]],t);
}
r[i]=max(r[i],t);
F(k,3,47){
if ((a[j]-a[i]*b[k].fi)%b[k].se==0){
t=2;
f[1]=a[i];f[2]=(a[j]-a[i]*b[k].fi)/b[k].se;
if (f[2]<0) continue;
F(p,3,60){
f[p]=f[p-1]+f[p-2];
if (f[p]>inf) break;
if (p>k){
if (q.find(f[p])!=q.en){
t++;
int wzp=q[f[p]];
l[wzp]=max(l[wzp],t);
}
}
}
r[i]=max(r[i],t);
}
}
}
}
l[1]=1;l[2]=2;r[n]=1;r[n-1]=2;
F(i,1,n) l[i]=max(l[i],l[i-1]);
D(i,n,1) r[i]=max(r[i+1],r[i]);
F(i,0,n) ans=max(ans,l[i]+r[i+1]);
wrn(ans);
return 0;
}