3357:[Usaco2004]等差数列

3357: [Usaco2004]等差数列

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 321 Solved: 153
[Submit][Status][Discuss]

Description

约翰发现奶牛经常排成等差数列的号码&＃xff0e;他看到五头牛排成这样的序号&＃xff1a;“1&＃xff0c;4&＃xff0c;3&＃xff0c;5&＃xff0c;7”

很容易看出“1&＃xff0c;3&＃xff0c;5&＃xff0c;7”是等差数列&＃xff0e;

给出N(1≤N≤2000)数字AI..AN(O≤Ai≤10^9)&＃xff0c;找出最长的等差数列&＃xff0c;输出长度&＃xff0e;

Input

第1行&＃xff1a;一个整数N.

第2到N&＃43;1行&＃xff1a;每行一个整数Ai&＃xff0c;表示牛的号码&＃xff0e;

Output

最长等差数列的长度&＃xff0e;

Sample Input

5
1
4
3
5
7

Sample Output

HINT

Source

Green

//f[i][j]表示当前等差数列最后一个数为a[i]&＃xff0c;倒数第二个数为j的最长长度
#include
#include
using namespace std;
int read(){register int x&＃61;0;bool f&＃61;1;register char ch&＃61;getchar();while(ch<&＃39;0&＃39;||ch>&＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)f&＃61;0;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;){x&＃61;x*10&＃43;ch-&＃39;0&＃39;;ch&＃61;getchar();}return f?x:-x;
}
const int N&＃61;1e5&＃43;10;
map<int,int>f[N];
int n,ans,a[N];
int main(){n&＃61;read();for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) a[i]&＃61;read();if(n&＃61;&＃61;1){puts("1");return 0;}for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;){for(int j&＃61;1;j){ans&＃61;max(ans,f[i][a[j]]&＃61;max(2,max(f[i][a[j]],f[j][2*a[j]-a[i]]&＃43;1)));//这里是等差中项
}}printf("%d",ans);return 0;
}