Description
An arithmetic series consists of a sequence of terms such that each term minus its immediate predecessor gives the same result. For example, the sequence 3, 7, 11, 15 is the terms of the arithmetic series 3+7+11+15; each term minus its predecessor equals 4. (Of course there is no requirement on the first term since it has no predecessor.)
Given a collection of integers, we want to find the longest arithmetic series that can be formed by choosing a sub-collection (possibly the entire collection).
Input
There are multiple cases, and each case contains 2 lines: the first line contains the count of integers (between 2 and 1000 inclusive), the following line contains all the integers (between -1,000,000,000 and 1,000,000,000 inclusive) separated by one or more spaces.
Output
Print a single number for each case in a single line.
Sample Input
7
3 8 4 5 6 2 2
4
-1 -5 1 3
4
-10 -20 -10 -10
Sample Output
5
3
3
Source
看了别人的解题报告说是DP+二分。试着写了一个后来发现与实际的结果相差2，不管三七二十一直接在原来的结果上加2。
竟然过了~o(╯□╰)o
cjx就在想这是为什么呢？后来发现因为我是从第三个数开始处理的，每个运算的结果都会少个2。
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <algorithm> 5 #define MAXN 1001 6 using namespace std; 7 8 int n,cnt; 9 int d[MAXN]; 10 int a[MAXN]; 11 int dp[MAXN][MAXN]; 12 13 int find(int l, int r, int v){ 14 while(l<=r){ 15 int m=(l+r)/2; 16 if(v==a[m])return m; 17 else if(v<a[m]){ 18 r=m-1; 19 }else if(v>a[m]){ 20 l=m+1; 21 } 22 } 23 return -1; 24 } 25 26 int main() 27 { 28 int ans,count; 29 int temp; 30 while( scanf("%d",&n)!=EOF ){ 31 for(int i=0; i<n; i++){ 32 scanf("%d",&d[i]); 33 } 34 sort(d,d+n); 35 cnt=0; 36 count=0; 37 ans=0; 38 temp=-1000000001; 39 for(int i=0; i<n; i++){ 40 if(d[i]!=temp){ 41 a[cnt++]=d[i]; 42 if(count>ans) 43 ans=count; 44 count=1; 45 }else{ 46 count++; 47 } 48 } 49 if(count>ans){ 50 ans=count; 51 } 52 memset(dp,0,sizeof(dp)); 53 for(int i=0; i<cnt; i++){ 54 for(int j=i+1; j<cnt; j++){ 55 int v=a[j]+a[j]-a[i]; 56 int k=-1; 57 k=find(j+1,cnt-1,v); 58 if(k!=-1){ 59 dp[j][k]=dp[i][j]+1; 60 if(dp[j][k]>=ans){ 61 ans=dp[j][k]; 62 } 63 } 64 } 65 } 66 printf("%d ",ans+2); 67 } 68 return 0; 69 }