提交地址:http://codevs.cn/problem/1006/
1006 等差数列
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
给定n(1<=n<=100)个数,从中找出尽可能多的数使得他们能够组成一个等差数列.求最长的等差数列的长度.
输入描述 Input Description
第一行是一个整数n,接下来一行包括了n个数,每个数的绝对值不超过10000000.
输出描述 Output Description
对于每个输入数据,输出你所找出的最长等差数列的长度
样例输入 Sample Input
7
3
8
4
5
6
2
2
样例输出 Sample Output
5
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm> #define N 100+10 using namespace std; int n;
int a[N];
int ans=;
int maxn=-;
bool visited[N]; //防止重复搜索 void dfs(int,int,int); int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
if(n==||n==)
{
printf("%d",n);
return ;
}
sort(a+,a+n+);
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
dfs(j,a[j]-a[i],i);
if(ans>maxn)
maxn=ans;
ans=;
memset(visited,,sizeof(visited));
}
printf("%d",maxn);
return ;
} void dfs(int x,int d,int last)//分别表示:搜到的位置,公差,上次的位置
{
if(x>n) return ;
if(visited[x]) return;
if(a[x]-a[last]!=d) return;
ans++;
for(int i=;i<=n-x;i++)
{
visited[x]=true;
dfs(x+i,d,x);
visited[x]=false;//递归还原条件
}
}