codevs 1006 等差数列

时间:2022-09-01 04:16:37

提交地址: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;//递归还原条件
}
}