51nod 1055 最长等差数列

1055 最长等差数列

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

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

Output

最长等差数列的长度。

Input示例

10
1
3
5
6
8
9
10
12
13
14

Output示例

5
————————————————————————
这道题可以写到n^2 f【i】【j】表示当前的等差数列以i结尾倒数第二个数是j的最大长度
然后发现倒数第三个数是单调递减的然后就可以写到严格n^2了

#include<stdio.h>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int M=10007;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();}
    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=getchar();}
    return ans*f;
}
LL n,mx,s[M];
unsigned short f[M][M];
int main(){
    n=read(); for(int i=1;i<=n;i++) s[i]=read();
    sort(s+1,s+1+n);
    for(int i=3;i<=n;i++){
        for(int j=i-1,k=i-2;k>0;j--){
            while(k>=1&&(s[i]+s[k])>(s[j]<<1)) k--;
            if(s[i]+s[k]==s[j]<<1&&(f[i][j]=f[j][k]+1)>mx) mx=f[i][j];
        }
    }printf("%d
",mx+2);
    return 0;
}