Codeforces Round #156 (Div. 1) A. Almost Arithmetical Progression DP

链接：

http://codeforces.com/contest/256/problem/A

题意：

给出一个序列，求最长的子序列，满足隔位的两个数相等，问这个最长的子序列的长度是多少。

题解：

先把b数组离散化一下，dp[i][j]就表示当前循环节是i,j的最大值

代码：

int n;
int b[MAXN];
int dp[MAXN][MAXN];

int main() {

ios::sync_with_stdio(false), cin.tie(0);

cin >> n;

VI v;

rep(i, 0, n) cin >> b[i], v.pb(b[i]);

sort(all(v));

v.erase(unique(all(v)), v.end());

rep(i, 0, n) b[i] = lower_bound(all(v), b[i]) - v.begin();

int m = v.size();

int ans = 0;

rep(i, 0, n) rep(j, 0, m) {

int x = b[i];

dp[j][x] = max(dp[j][x], dp[x][j] + 1);

ans = max(ans, dp[j][x]);

}

cout << ans << endl;

return 0;
}