zoj 2672 Fibonacci Subsequence(hash + dp)

zoj 2672 Fibonacci Subsequence(hash + dp)

题目：​​Subsequence

Time Limit: 5 Seconds       Memory Limit: 32768 KB       Special Judge

A sequence of integer numbers a1 , a2 , ..., an is called a Fibonacci sequence if ai = ai-2+ai-1 for all i=3,4,...,n.

Given a sequence of integer numbers c1 , c2 , ..., cm you have to find its longest Fibonacci subsequence.

Input

There are several test cases in the input. The first line of each case contains  m  ( 1 <= m <= 3,000 ). Next line contains  m  integer numbers not exceeding  109

by their absolute value.

There is a new line between each case.

Output

On the first line of each case print the maximal length of the Fibonacci subsequence of the given sequence. On the second line print the subsequence itself.

There is a new line between each case.

Example

寻找的大致思路：前面选择两个数字，两者的和是我们要找的目标，在后面寻找，能找到就增加长度。这样下来，时间复杂度是O(n^3)，对于m<=3000来讲是不行的。C++ 中的hash_map是个好东西，查找效率是常数级别，基础是哈希表，以空间换时间，map也能构造映射关系查找，查找效率是O(logn)，基础是rb_tree红黑树。在大多数情况下哈希的效率更高。但某些情况不如map。由多个个体构造极值情况：DP。因为已经用了hash，所以DP数组可以用short int。short int 的取值范围是-32768----32767。不然会MLE。

#include #include #include #include using namespace std;using __gnu_cxx::hash_map;const int maxn=3010;hash_map mymap;hash_map::iterator ix;void show(){ for(ix=mymap.begin();ix!=mymap.end();ix++){ cout<first<<" "<second<<" "; } cout<>n){ if(!first)puts(""); first=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++)dp[i][j]=1; } mymap.clear(); int top=0,low=a[1],high; for(int i=n;i>=1;i--){ for(int j=1;jsecond]+1; // 小下标 --- 大下标 if(dp[j][i]>top){ top=dp[j][i]; low=j; high=i; } } } mymap[a[i]]=i; } if(n==1){ printf("1\n%d\n",a[1]); continue; } if(n==2) { printf("2\n%d %d\n",a[1],a[2]); continue; } if(top==0){ printf("2\n%d %d\n",a[1],a[2]); continue; } printf("%d\n",top+1); printf("%d",a[low]); int q1=a[low],q2=a[high]; for(int i=0;i

又犯了逻辑错误，主函数的结果处理如果是这样是WA的：

if(n==1){ printf("1\n%d\n",a[1]); } else if(n==2) { printf("2\n%d %d\n",a[1],a[2]); continue; } if(top==0){ printf("2\n%d %d\n",a[1],a[2]); } else { printf("%d\n",top+1); printf("%d",a[low]); int q1=a[low],q2=a[high]; for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。