题意:给出一个序列b,求 b 中形如p, p - q, p, p - q, p, p - q, ... 这样出现的最长子序列的长度 (1 ≤ n ≤ 4000, 1 ≤ bi ≤ 10 ^ 6)。
题目链接:http://codeforces.com/problemset/problem/255/C
——>>状态:dp[i][j] 表示满足条件的最后两个数是 bi 和 bj 的子序列长度。。
状态转移方程:dp[i][j] = dp[last][i] + 1;(last 是小于 i 的但离 i 最近的 b[last] == b[j] 成立的位置)。。
#include <cstdio> #include <algorithm> using std::max; const int MAXN = 4000 + 10; int n; int b[MAXN]; int dp[MAXN][MAXN]; void Read() { for (int i = 1; i <= n; ++i) { scanf("%d", b + i); } } void Dp() { int ret = 0; dp[0][0] = 0; for (int j = 1; j <= n; ++j) { for (int i = 0, last = 0; i < j; ++i) { dp[i][j] = dp[last][i] + 1; if (b[i] == b[j]) { last = i; } ret = max(ret, dp[i][j]); } } printf("%d\n", ret); } int main() { while (scanf("%d", &n) == 1) { Read(); Dp(); } return 0; }