bzoj 3357: [Usaco2004]等差数列
Contents
3357: [Usaco2004]等差数列
Time Limit: 10 Sec Memory Limit: 128 MB
Description
约翰发现奶牛经常排成等差数列的号码．他看到五头牛排成这样的序号：“1，4，3，5，7”
很容易看出“1，3，5，7”是等差数列．
给出N(1≤N≤2000)数字AI..AN(O≤Ai≤10^9)，找出最长的等差数列，输出长度．
Input
第1行：一个整数N.
第2到N+1行：每行一个整数Ai，表示牛的号码．
Output
最长等差数列的长度．
Sample Input
5
1
4
3
5
7
1
4
3
5
7
Sample Output
4
HINT
#include<map>
#include<cstdio>
#define M 2020
using namespace std;
int n,ans,a[M];
map<int,int>f[M];
int main()
{
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
if(n==1)printf("1");
else{
for(i=1;i<=n;i++)
for(j=1;j<i;j++)
{
f[i][a[j]]=max(f[i][a[j]],2);
f[i][a[j]]=max(f[i][a[j]],f[j][a[j]*2-a[i]]+1);
ans=max(ans,f[i][a[j]]);
}
printf("%d",ans);}
}
发表评论