最长等差数列 51Nod - 1055

本文主要是介绍最长等差数列 51Nod - 1055，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.51nod.com/Challenge/Problem.html#!#problemId=1055

dp[i][j]代表以a[i] a[j]为最后两项的等差数列的长度 对于等差数列有2*b[i]=b[i-1]+b[i+1] 如果对于某个等差数列 我们已经找到了b[i-1]+d=b[i] 如果再找到b[i]+d=b[i+1]那就可以把b[i+1]加到该等差数列末尾 然后抓住b[i-1] b[i] b[i+1]的中间项b[i]向两边扩展转移即可

 

 

 

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;short dp[maxn][maxn];
int ary[maxn];
int n;int main()
{int i,j,k,ans;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d",&ary[i]);sort(ary+1,ary+n+1);for(i=1;i<=n;i++){for(j=i+1;j<=n;j++){dp[i][j]=2;}}ans=2;for(j=n-1;j>=2;j--){i=j-1,k=j+1;while(1<=i&&k<=n){if(ary[i]+ary[k]<2*ary[j]) k++;else if(ary[i]+ary[k]>2*ary[j]) i--;else{dp[i][j]=dp[j][k]+1;ans=max(ans,(int)(dp[i][j]));i--,k++;}}}printf("%d\n",ans);return 0;
}

 

这篇关于最长等差数列 51Nod - 1055的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---