[文章目录]
Description
约翰发现奶牛经常排成等差数列的号码．他看到五头牛排成这样的序号：“1，4，3，5，7”很容易看出“1，3，5，7”是等差数列． 给出N(1≤N≤2000)数字AI..AN(O≤Ai≤10^9)，找出最长的等差数列，输出长度．n<=2000
假设以i结尾，如果上一个元素确定了的话，这个等差数列就确定了。也就是说，两个元素确定一个等差数列。
设dp[i][j]表示以第i个元素结尾，第j个元素为倒数第二的元素的最长等差数列的长度。那么，j前面的元素可以确定，为a[j]*2-a[i]，根据贪心策略，只要找到j前面最后的一个大小为a[j]*2-a[i]的id。转移：dp[i][j]=dp[j][k]+1;
把数列离散化，然后把么个数投影到数组的一个id上。再开一个二维数组维护一下j前面的第一个某数的id就好了。
复杂度n^2logn
然而好像还挺快的。。。rank 10
#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,a[2100],dp[2100][2100],ans=1;
int id[2100][2100],tot,b[2100],c[2100];
int getid(int x)
{
int l=1,r=tot+1,mid;
while(l<r)
{
mid=l+r>>1;
if(x<=c[mid]) r=mid;
else l=mid+1;
}
return r;
}
int main()
{
scanf("%d",&n); int i,j,x;
for(i=1;i<=n;++i) scanf("%d",a+i),b[i]=a[i];
sort(b+1,b+n+1); c[1]=b[1]; tot=1;
for(i=2;i<=n;++i) if(b[i]!=b[i-1]) c[++tot]=b[i];
for(i=1;i<=n;++i)
{
for(j=1;j<i;j++)
{
x=getid(a[j]+a[j]-a[i]);
if(c[x]==a[j]+a[j]-a[i]) dp[i][j]=dp[j][id[j-1][x]]+1;
else dp[i][j]=2;
}
dp[i][0]=1;
for(j=1;j<=tot;++j) id[i][j]=id[i-1][j];
id[i][getid(a[i])]=i;
}
for(i=1;i<=n;++i)
for(j=1;j<i;j++)
ans=max(ans,dp[i][j]);
printf("%d",ans);
return 0;
}