一道dp[不太好写]

http://acm.csu.edu.cn:20080/csuoj/problemset/problem?pid=2281

Description

An arithmetic progression is a sequence of numbers a1, a2, ..., ak where the difference of consecutive members ai + 1 − ai is a constant 1 ≤ i ≤ k − 1 . For example, the sequence 5, 8, 11, 14, 17 is an arithmetic progression of length 5 with the common difference 3.

In this problem, you are requested to find the longest arithmetic progression which can be formed selecting some numbers from a given set of numbers. For example, if the given set of numbers is {0, 1, 3, 5, 6, 9}, you can form arithmetic progressions such as 0, 3, 6, 9 with the common difference 3, or 9, 5, 1 with the common difference -4. In this case, the progressions 0, 3, 6, 9 and 9, 6, 3, 0 are the longest.

Input

The input consists of a single test case of the following format.

n v1 v2 ... vn

n is the number of elements of the set, which is an integer satisfying 2 ≤ n ≤ 5000 . Each vi(1 ≤ i ≤ n) is an element of the set,which is an integer satisfying 0 ≤ vi ≤ 109.vi's are all different, i.e.,vi ≠ vj if i ≠ j

Output

Output the length of the longest arithmetic progressions which can be formed selecting some numbers from the given set of numbers.

Sample Input

6 0 1 3 5 6 9

Sample Output

4题意：求出序列从小到大排序之后能形成的最长等差数列的长度。题解：dp,dp[i][j]表示i和j作为前两项时的数列长度，如果先枚举第一项(O(N)),然后第二项如果和第三项在第一项的同一侧的话就是(O(N^2))，整体复杂度是(O(N^3))，难以接受，而如果先枚举第二项，然后第一项和第三项在第二项两侧，根据a[j]+a[k]=2*a[i]可以将复杂度降为O(N^2) 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int a[5005],dp[5005][5005]; 7 int main(){ 8 int n; 9 scanf("%d",&n); 10 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 11 for(int i=1;i<=n;i++){ 12 for(int j=i;j<=n;j++){ 13 if(i!=j)dp[i][j]=2; 14 else dp[i][j]=1; 15 } 16 } 17 sort(a+1,a+1+n); 18 int ans=2; 19 for(int i=n-1;i>=2;i--){ 20 int j=i-1; 21 int k=i+1; 22 while(j>=1&&k<=n){ 23 if(a[j]+a[k]==2*a[i]){dp[j][i]=dp[i][k]+1;ans=max(ans,dp[j][i]);k++;j--;} 24 else if(a[j]+a[k]<2*a[i]){k++;} 25 else {j--;} 26 } 27 } 28 cout<<ans<<endl; 29 return 0; 30 } View Code

 

转载于:https://www.cnblogs.com/MekakuCityActor/p/10611585.html