---

最长等差数列(51nod 1055)

Description

N个不同的正整数，找出由这些数组成的最长的等差数列。

例如：1 3 5 6 8 9 10 12 13 14

等差子数列包括(仅包括两项的不列举）

1 3 5

1 5 9 13

3 6 9 12

3 8 13

5 9 13

6 8 10 12 14

其中6 8 10 12 14最长，长度为5。

Input Format

第1行：N，N为正整数的数量(3 <= N <= 10000)。 第2 - N+1行：N个正整数。(2<= A[i] <= 10^9)

Output Format

最长等差数列的长度。

Sample Input

10 1 3 5 6 8 9 10 12 13 14

Sample Output

5

解析

对于一个序列的特定最优值求解，应该很容易想到是线性DP。第一步首先排序是很容易想到的。

第一个突破口在状态的设置，如果直接用n设置状态，发现会很难处理转移的问题。

\(f[i][j]\)代表以\(a_i\)为第一项，\(a_j\)为第二项所构成的等差数列的最长长度\((i<j)\)

考虑若\(a_k\)可以作为这个等差数列的第三项，且满足\((i<j<k)\)，那么\(f[i][j]=f[j][k]+1\)。

由等差数列的性质可以得知，当\(a_k\)可以作为第三项时：\(a_j*2=a_i+a_k\)。

此时我们枚举\(j\)，将\(i\)，\(k\)设为指针利用性质的大小关系去扫描即可，可以做到时间复杂度\(O(n^2)\)。

当然，由于\((i<j<k)\)，所以转移时需要倒序枚举。

\(Code:\)

#include
    
     using namespace std;inline void read(int &k){    int w=0,x=0;char ch;    while(!isdigit(ch))w|=ch=='-',ch=getchar();    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();    k=(w?-x:x);return;}const int N=10000+80;int n,a[N];short int f[N][N]={},ans=2;inline void input(void){    read(n);    for(int i=1;i<=n;i++)read(a[i]);}inline void init(void){    sort(a+1,a+n+1);    for(int i=1;i
     
      =2;j--)    {        int i=j-1,k=j+1;        while(i>=1&&k<=n)        {            if(a[j]*2==a[i]+a[k])            {                f[i][j]=f[j][k]+1;                ans=max(ans,f[i][j]);                k++,i--;             }            if(a[j]*2>a[i]+a[k])k++;            if(a[j]*2
     
    

考点：灵活的状态设置。

---