算法

(线段树优化DP) $O(N\log K)$

令 $dp[i][j]$ 表示前 $i$ 个数中以 $j$ 结尾满足要求的最长子列的长度

状态转移：

$$ dp[i][A_i] = \max(dp[i - 1][A_i - K], \cdots, dp[i - 1][A_i + K]) + 1 $$

在空间上我们可以利用滚动数组压掉一维
而在时间上计算量为 $O(NK)$，显然会超时

你知道如何优化时间吗？我知道。
利用线段树即可。

C++ 代码

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

const int MAX_A = 300005;

int op(int a, int b) { return max(a, b); }
int e() { return 0; }

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    rep(i, n) cin >> a[i];

    segtree<int, op, e> dp(MAX_A);
    rep(i, n) {
        int x = a[i];
        int l = x - k, r = x + k + 1;
        l = max(l, 0);
        r = min(r, MAX_A);
        int now = dp.prod(l, r) + 1;
        dp.set(x, max(dp.get(x), now));
    }

    int ans = dp.prod(0, MAX_A);
    cout << ans << '\n';

    return 0;
}