解答:https://atcoder.jp/contests/abc339/submissions/49982630
解法:解説AC。dp[i][x]を「数列をi番目まで見たとき、①そのi番目の数がxであればi番目まででできる題意を満たす部分列の最大長、②そのi番目の数が0でなければ0」というdp配列を考える。 このとき、dpの遷移は以下となる。
dp[i][x] = max(dp[j][x]) (x = , j < i, x - D ≦ ≦ x + D)
よって、dp配列を最大値取得のセグ木で持たせ、各について、そのの±Dに存在するの最大値をセグ木で取得しつつ、セグ木を更新してゆけばよい。
(こういうの何度か見ている気がするが、苦手…)