题意：应该比较好理解
分析：这道题可以有两种方法：一种就是简单dp;还有一种就是直接查找。
第一种方法：我们假设dp[i][j]代表从i->j位置满足等间距的数目的个数，那么我们可以在i之前设置位置l,来寻找a[j]-a[i[==a[i]-a[l];
AC代码：
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 const int maxn = 5010; 7 #define LL long long 8 #define INF 0x3f3f3f3f 9 int n,ans=0;; 10 int a[maxn]; 11 int dp[maxn][maxn]; 12 13 int main(){ 14 scanf("%d",&n); 15 for(int i=0;i<n;i++){ 16 scanf("%d",&a[i]); 17 } 18 memset(dp,0,sizeof(dp)); 19 sort(a,a+n); 20 for(int i=0;i<n;i++) dp[i][i]=1; 21 for(int i=0;i<n;i++){ 22 int l=i-1; 23 for(int j=i+1;j<n;j++){ 24 dp[i][j]=2; 25 while(l>=0&&a[j]-a[i]>a[i]-a[l]) l--; 26 if(l>=0&&a[j]-a[i]==a[i]-a[l]){ 27 dp[i][j]=max(dp[i][j],dp[l][i]+1); 28 // ans=max(ans,dp[i][j]); 29 } 30 ans=max(ans,dp[i][j]); 31 } 32 } 33 printf("%d\n",ans); 34 35 return 0; 36 } 37 38 /* 39 6 0 1 3 5 6 9 40 */
第二种方法：看了dalao的代码，感觉有些地方设置的十分巧妙，直接上代码理解吧！
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<set> 5 #include<map> 6 #include<algorithm> 7 using namespace std; 8 const int maxn = 5010; 9 #define LL long long 10 #define INF 0x3f3f3f3f 11 int n; 12 LL a[maxn]; 13 set<LL> se; 14 15 int main(){ 16 scanf("%d",&n); 17 int ans=2; 18 for(int i=0;i<n;i++){ 19 scanf("%lld",&a[i]); 20 se.insert(a[i]); 21 } 22 sort(a,a+n); 23 for(int i=0;i<n;i++){ 24 for(int j=i+1;j<n;j++){ 25 LL d=a[j]-a[i]; 26 int cnt=2; 27 if(!se.count(a[i]+ans*d)) continue;//在这里一定是ans*d,而不能是cnt*d，不然会超时，这里设置的非常精妙，值得学习。 28 while(se.count(a[i]+cnt*d)) cnt++; 29 ans=max(ans,cnt); 30 } 31 } 32 printf("%d\n",ans); 33 34 35 return 0; 36 } 37 38 /* 39 6 0 1 3 5 6 9 40 */
Arithmetic Progressions Gym - 102082B
原文：https://www.cnblogs.com/Bravewtz/p/11372630.html