CF - 255C - Almost Arithmetical Progression（dp）

题意：给出一个序列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("%dn", ret);
}
int main()
{
while (scanf("%d", &n) == 1)
{
Read();
Dp();
}
return 0;
}

最后

以上就是如意鸡为你收集整理的CF - 255C - Almost Arithmetical Progression（dp）的全部内容，希望文章能够帮你解决CF - 255C - Almost Arithmetical Progression（dp）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。