题目大意：给你一个长度为n(2<=n<=5000)的序列，没有重复的数字，序列中每个元素满足(0<=numi<=1e9)。求一个最长的数列满足差分值相同（除n=2外，可以看成等差数列）。输出这个最大长度。
算法梗概：DP。看了几篇博客都说算是个板子套路DP题。在做的时候也想到了DP，但是没找对状态。
另外可以用其他算法来做这道题，后面慢慢补。先给出DP算法的代码和思路。
1 #include2 #include 3 const int maxn = 5e3 + 5; 4 int dp[maxn][maxn],n,num[maxn]; 5 int main() 6 { 7 scanf("%d",&n); 8 for(int i=1;i<=n;++i){ 9 scanf("%d",num+i);10 for(int j=1;j<=n;++j){11 dp[i][j] = 2;12 }13 }14 std::sort(num+1,num+1+n);15 int ans = 2;16 for(int i=1;i<=n-1;++i){17 int pre = i - 1;18 for(int j=i+1;j<=n;++j){19 ///令d=num[j] - num[i],因为序列是递增的，所以num[i] - num[pre]在pre刚开始不满足条件时大于d，在pre刚好满足条件时等于d，继续遍历则小于d，后来的遍历是无意义的所以跳出即可20 while(pre > 0 && num[j] - num[i] > num[i] - num[pre]) pre--;21 if(pre==0) break;22 else if(pre > 0 && num[j] - num[i] == num[i] - num[pre]) dp[i][j] = std::max(dp[i][j],dp[pre][i]+1);23 ans = std::max(ans,dp[i][j]);24 }25 }26 printf("%d\n",ans);27 return 0;28 }
DP思路：dp[i][j]表示已下标i，j（i<j）为结尾两个元素的一个子序列的长。枚举i，以i+1开始向后遍历j，这样对于每对i，j我们可以求出他们的差，以这个差为标准，从i-1开始向前遍历记为pre，直到找到的pre和i，j满足num[j] - num[i] == num[i] - num[pre]。如果找到这样的num[pre]更新dp[i][j]即可。
状态转移方程：dp[i][j] = max(dp[i][j],dp[pre][i]+1)
直接用用等差数列的通项公式来暴力
1 #include2 #include 3 #include 4 using namespace std; 5 const int maxn = 5e3+50; 6 int num[maxn],n; 7 set se; 8 int main() 9 {10 scanf("%d",&n);11 for(int i = 1; i<=n; ++i)12 {13 scanf("%d",num+i);14 se.insert(num[i]);15 }16 sort(num+1,num+n+1);17 int ans = 2,d,k;18 for(int i=1;i<=n;++i)19 {20 for(int j=i+1;j<=n;++j)21 {22 k = 2,d = num[j] - num[i];23 if(!se.count(num[i] + ans*d)) continue;24 while(se.count(num[i] + k*d)) k++;25 ans = max(ans,k);26 }27 if(ans==n) break;28 }29 printf("%d\n",ans);30 return 0;31 }
核心代码：
1 k = 2,d = num[j] - num[i];2 if(!se.count(num[i] + ans*d)) continue;3 while(se.count(num[i] + k*d)) k++;4 ans = max(ans,k);
暴力思路：ak = a1 + (k-1)d;
两层for循环来枚举a1和d，对于每对<a1,d>,枚举k来得到一个ak，判断ak是不是存在在序列中，存在继续枚举，否则更新答案。
请注意！！！ if(!se.count(num[i] + ans*d)) continue; 这行代码的作用，对于你已经更新到的答案ans，如果num[i] + ans*d都不存在，那么无法更新答案，所以跳过这层循环。
没有这行代码会TLE在test 57或者test 58，做题就死在了这里了。
还有些同学用了二分函数，其实和暴力的核心思想差不多，用二分函数优化很多，这里只给代码，不解释了如果暴力看懂了这个也就懂了
1 #include2 #include 3 const int maxn = 5e3 + 5; 4 int dp[maxn][maxn],n,num[maxn]; 5 int main() 6 { 7 scanf("%d",&n); 8 for(int i=1;i<=n;++i) scanf("%d",num+i); 9 std::sort(num+1,num+1+n);10 11 int ans = 2,res,d,pos;12 for(int i=1;i<=n-1;++i){13 for(int j=i+1;j<=n;++j){14 d = num[j] - num[i];15 res = 2;16 pos = std::lower_bound(num+j+1,num+n+1,num[i]+ans*d) - num;17 if(num[pos]!=num[i]+ans*d) continue;18 for(int k=j;k<=n-1;){19 pos = std::lower_bound(num+k+1,num+n+1,num[k]+d) - num;20 if(num[pos]==num[k]+d){21 k = pos;22 res++;23 }24 else break;25 }26 ans = std::max(ans,res);27 }28 }29 printf("%d\n",ans);30 return 0;31 }
This’s all！如有错误，请评论指正谢谢！！