SRM 512 Div1 Med SubFibonacci
問題概要
問題文を読んでください。
まず数列を二つに分けて、それぞれの最大値の合計の最大値を求める。
分けたあとの数列の任意の2組を取ってきて、小さいほうを初項、大きいほうをx番目として、フィボナッチ数列を計算して、含まれる要素の数をかぞえる。(x番目と仮定すれば第二項はO(1)でもとまる[もちろん基本のフィボナッチ数列は前もって計算])
最初、第二項が第一項よりも大きいという条件を入れていてハマった。
4 1 5 6 から 4 5 6を取り出すのはOK.あらかじめソートしておいて、選んだ組の小さいほうから順にみていけば、4 1 5 6を取り出すようなことは防げる。
#include <algorithm> #include <vector> #include <set> using namespace std; typedef long long ll; #define pb push_back class SubFibonacci { public: vector<ll> s; ll fib[50]; int solve(int x) { int ans1=0,ans2=0; ans1 = min(2,x); ans2 = min(2,(int)s.size()-x); set<ll> s1,s2; for(int i=0;i<x;i++)s1.insert(s[i]); for(int i=x;i<s.size();i++)s2.insert(s[i]); for(int i=0;i<x;i++) { for(int j=i+1;j<x;j++) { for(int k=1;k<40;k++) { ll r=s[j]-s[i]*fib[k]; if(r%fib[k+1]==0&&r/fib[k+1]>0) { int b = r/fib[k+1]; int cnt=0; for(int l=0;l<40;l++) { if(s1.find(s[i]*fib[l]+b*fib[l+1])!=s1.end())cnt++; } ans1 = max(ans1,cnt); } } } } for(int i=x;i<s.size();i++) { for(int j=i+1;j<s.size();j++) { for(int k=1;k<40;k++) { ll r=s[j]-s[i]*fib[k]; if(r%fib[k+1]==0&&r/fib[k+1]>0) { int b = r/fib[k+1]; int cnt=0; for(int l=0;l<40;l++) { if(s2.find(s[i]*fib[l]+b*fib[l+1])!=s2.end())cnt++; } ans2 = max(ans2,cnt); } } } } return ans1+ans2; } int maxElements(vector <int> S) { sort(S.begin(),S.end()); for(int i=0;i<S.size();i++)s.pb((ll)S[i]); fib[0]=1;fib[1]=0; for(int i=2;i<=42;i++)fib[i]=fib[i-1]+fib[i-2]; int ans=0; for(int i=0;i<s.size();i++)ans = max(ans,solve(i)); return ans; } };