「51nod 1055」最长等差数列

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

Constraints

$ n \leq 10000$

Solution

dp(i,j)dp(i,j) 表示等差数列最后的两个数字的位置。

转移的时候考虑先固定 jj 的位置,然后分别向两边扫寻找满足 ai+ak=2aja_i+a_k=2\cdot a_j 的数对 (i,k)(i,k) ,并用 dp(i,j)+1dp(i,j)+1 来更新 dp(j,k)dp(j,k)

考虑到空间问题,需要使用 short int 。时间复杂度 O(n2)O(n^2)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const int N=1e4+5;
int n,a[N];
short int t,ans=2,dp[N][N];
int read()
{
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int main()
{
n=read();
for(int i=1;i<=n;i++)a[i]=read();
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
dp[i][j]=2;
for(int j=2;j<n;j++)
{
int i=j-1,k=j+1;
while(i>=1&&k<=n)
{
if(a[i]+a[k]<2*a[j])k++;
else if(a[i]+a[k]>2*a[j])i--;
else
{
t=dp[i][j]+1;
dp[j][k]=max(dp[j][k],t);
ans=max(ans,t);
i--;k++;
}
}
}
printf("%d\n",ans);
return 0;
}