codevs——T1006 等差数列

http://codevs.cn/problem/1006/

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

给定n(1<=n<=100)个数,从中找出尽可能多的数使得他们能够组成一个等差数列.求最长的等差数列的长度.

输入描述 Input Description

第一行是一个整数n,接下来一行包括了n个数,每个数的绝对值不超过10000000.

输出描述 Output Description

对于每个输入数据,输出你所找出的最长等差数列的长度

样例输入 Sample Input

样例输出 Sample Output

爆搜

 1 #include <algorithm>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 
 6 int n,num[115],ans,cnt;
 7 
 8 void DFS(int pos,int poor)
 9 {
10     if(pos==n+1) return ;
11     for(int i=pos+1;i<=n;i++)
12     {
13         if(num[i]-num[pos]==poor)
14         cnt++,DFS(i,poor);
15     }
16 }
17 
18 int main()
19 {
20     scanf("%d",&n);
21     for(int i=1;i<=n;i++)
22         scanf("%d",num+i);
23     if(n==1)
24     {
25         puts("1");
26         return 0;
27     }
28     sort(num+1,num+n+1);
29     for(int i=1;i<n;i++)
30         for(int j=i+1;j<=n;j++) 
31         {
32             cnt=1;
33             DFS(i,num[j]-num[i]);
34             ans=max(ans,cnt);
35         }
36     printf("%d",ans);
37     return 0;
38 }

——每当你想要放弃的时候，就想想是为了什么才一路坚持到现在。