Codeforces CF255C Almost Arithmetical Progression

链接
难度：\(1500\)

有一个序列 \(b_{1\sim n}\)。

你需要从中选出一个长度最长的子序列 \(p_{1\sim k}\)，使其满足 \(p_1=p_3=...=p_{\lceil\frac{k}{2}\rceil-1},p_2=p_4=...=p_{\lfloor\frac{k}{2}\rfloor\times2}\)。

数据范围：\(n\le 4000, b_i\le 10^6\)。

令 \(dp_{i,j}\) 为到第 \(i\) 个数结尾为 \(j\) 的不包括 \(i\)的最长长度。

则 \(dp_{i,j}\) 只有可能由前面以 \(b_i\) 结尾的序列推来，所以可得 \(dp_{i,j}=max\{dp_{k,b_i}\}(k<i)\)。

因为维护的是不包括 \(i\)，所以最终答案需 \(+1\)。

发现 \(b_i\le 10^6\)，\(O(n\max\{b_i\}\) 明显不可过，则进行离散化，时间复杂度 \(O(n^2)\)。

// Problem: C. Almost Arithmetical Progression
// Contest: Codeforces - Codeforces Round #156 (Div. 2)
// URL: https://codeforces.com/problemset/problem/255/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

# include <bits/stdc++.h>
using namespace std;
map <int, int> mp;
const int N = 4000;
int a [N + 10], dp [N + 10] [N + 10];
int main () {
	ios :: sync_with_stdio (false);
	cin .tie (0);
	cout .tie (0);
	int n;
	cin >> n;
	int m = 0;
	for (int i = 1; i <= n; ++ i) {
		cin >> a [i];
		if (! mp [a [i]]) {
			mp [a [i]] = ++ m;
		}
		a [i] = mp [a [i]];// 这里要先修改好，不然后面每一次转移都要带一个 log 时间复杂度为 O (n ^ 2 log n) 会被卡 
	}
	int ans = 0;
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j < i; ++ j) {
			dp [i] [a [j]] = max (dp [i] [a [j]], dp [j] [a [i]] + 1);
			ans = max (ans, dp [i] [a [j]]);
		}
	}
	cout << ans + 1;
	return 0;
}