題干：

Gena loves sequences of numbers. Recently, he has discovered a new type of sequences which he called an almost arithmetical progression. A sequence is an?almost arithmetical progression, if its elements can be represented as:

• a1?=?p, where?p?is some integer;
• ai?=?ai?-?1?+?(?-?1)i?+?1·q?(i?>?1), where?q?is some integer.

Right now Gena has a piece of paper with sequence?b, consisting of?n?integers. Help Gena, find there the longest subsequence of integers that is an almost arithmetical progression.

Sequence?s1,??s2,??...,??sk?is a subsequence of sequence?b1,??b2,??...,??bn, if there is such increasing sequence of indexes?i1,?i2,?...,?ik?(1??≤??i1??<??i2??<?... ??<??ik??≤??n), that?bij??=??sj. In other words, sequence?s?can be obtained from?b?by crossing out some elements.

Input

The first line contains integer?n?(1?≤?n?≤?4000). The next line contains?n?integers?b1,?b2,?...,?bn?(1?≤?bi?≤?106).

Output

Print a single integer — the length of the required longest subsequence.

Examples

Input

2 3 5

Output

2

Input

4 10 20 10 30

Output

3

Note

In the first test the sequence actually is the suitable subsequence.

In the second test the following subsequence fits:?10,?20,?10.

題目大意：

? ?給出一個序列，求最長的子序列，滿足隔位的兩個數相等，問這個最長的子序列的長度是多少。

解題報告：

? 想了好久想到一個dp方程，抱著冒險的心態o(n^2)交一發，TLE41了，，，把離散化的數組提前預處理了一下，，，又莽了一發，，AC了。。小驚喜。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 1e6+5; int dp[4004][4004]; int a[4004],b[4004]; int cnt[MAX]; int pos[MAX]; int len,n; int get(int x) {return lower_bound(b+1,b+len+1,x) - b; } int main() {cin>>n;for(int i = 1; i<=n; i++) scanf("%d",a+i),b[i] = a[i],cnt[a[i]]++;sort(b+1,b+n+1);len = unique(b+1,b+n+1) - b - 1;for(int i = 1; i<=n; i++) pos[a[i]] = get(a[i]);for(int i = 1; i<=n; i++) for(int j = 1; j<=n; j++)dp[pos[a[i]]][pos[a[j]]] = 1;for(int i = 1; i<=n; i++) {for(int j = 1; j<i; j++) {if(a[i]!=a[j])dp[pos[a[i]]][pos[a[j]]] = dp[pos[a[j]]][pos[a[i]]]+1;}}int maxx = -1;for(int i = 1; i<=n; i++) {for(int j = 1; j<=n; j++) {maxx = max(maxx,dp[pos[a[i]]][pos[a[j]]]);}}for(int i = 1; i<=n; i++) {maxx = max(maxx,cnt[a[i]]);}printf("%d\n",maxx);return 0 ;}

貼一個題解

再貼一個題解

總結：

? ?思維過程是這樣的，，剛開始想暴力（用vector存權值啊之類的亂搞），，一想肯定不行，，有太多重復操作了。。然后想各種優化后來發現就是要求個序列，，所以跟最長上升子序列聯系起來了，，后來發現還真可以寫出來個遞推式，，但是是o(n^2)的不知道會不會T，，而且1600W的數組大小不知道會不會MLE，，交一發，WA，，造樣例，，發現全是同一個數的時候就會爆炸，，我就想，，再多也不可能超過數組長度啊，，所以就像把元素相等的時候特判一下（并沒想過正確性），改代碼，，測樣例，，沒啥問題，，再交一發，TLE41，，，失望（但是還是有點小驚喜的因為跑起來了最起碼說明算法的問題不大）。再想優化，開個數組預處理一波，去掉了時間復雜度的log，再交，AC。

總結

以上是生活随笔為你收集整理的【CodeForces - 255C】Almost Arithmetical Progression （dp，离散化）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。