51nod 1055：最长等差数列

1055 最长等差数列

基准时间限制：2 秒空间限制：262144 KB 分值: 80 难度：5级算法题

取消关注

N个不同的正整数，找出由这些数组成的最长的等差数列。

例如：1 3 5 6 8 9 10 12 13 14

等差子数列包括(仅包括两项的不列举）

1 3 5

1 5 9 13

3 6 9 12

3 8 13

5 9 13

6 8 10 12 14

其中6 8 10 12 14最长，长度为5。

Input

第1行：N，N为正整数的数量(3 <= N <= 10000)。
第2 - N+1行：N个正整数。(2<= A[i] <= 10^9)

Output

最长等差数列的长度。

Input示例

Output示例

真的是被上面的hash给忽悠了，一直想着顺序找然后找对应位置，结果TLE了一个下午。。。郁闷。。。
最后自己发现了一篇论文，看了上面的代码才过的。。。
代码：

#include <iostream>  
#include <algorithm>  
#include <cmath>  
#include <vector>  
#include <string>  
#include <cstring>  
#pragma warning(disable:4996)  
using namespace std;

#define maxn 10005
int n;
int a[maxn];
short int dp[maxn][maxn];

int main()
{
	//freopen("i.txt","r",stdin);
	//freopen("o.txt","w",stdout);
	int i,j,k,x,diff,ans,temp;
	scanf("%d",&n);
	
	for(i=0;i<n;i++)
		scanf("%d",a+i);
	memset(dp,0,sizeof(dp));
	sort(a,a+n);

	ans=0;
	for(i=1;i<n-1;i++)
	{
		j=i-1;
		k=i+1;
		while(j>=0 && k<n)
		{
			if(a[j]+a[k]>2*a[i])
			{
				j--;
			}
			else if(a[j]+a[k]<2*a[i])
			{
				k++;
			}
			else
			{
				dp[i][k]=dp[j][i]==0?3:dp[j][i]+1;
				if(dp[i][k]>ans)
				{
					ans=dp[i][k];
				}
				j--;
				k++;
			}
		}
	}
	printf("%d
",ans);
	//system("pause");
	return 0;
}