题干：
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。
京公网安备 11010502036488号