移動によって足場の高さは常に狭義単調減少します。よって、高さが小さい足場からその足場を最初に選んだ時にあり得る移動回数の最大値を動的計画法を用いて計算できます。

\(dp_i\) を最初に足場 i に移動した時にあり得る移動回数の最大値 とします。このとき、答えは \(dp\) の最大値です。 また、数列 \(p\) を \(p_{H_i}=i\) となるような数列とします。

この時、\(dp\) は以下のようにして求められます。

• \(dp=(0,0,\ldots,0)\) と初期化する
• \(i=1,2,\ldots,N\) の順で以下を行う
  • \(|p_i-j| \leq R, H_j \leq i-D\) を満たす \(j\) について、\(dp_{p_i} \leftarrow \max(dp_{p_i},dp_j+1)\)

各 \(i\) について条件を満たす \(j\) を列挙するような方法では 時間計算量 \(\mathrm{O}(ND)\) や \(\mathrm{O}(NR)\) となり、実行時間制限に収めることは難しいです。

各 \(i\) について条件を満たす \(j\) を列挙する部分を整理し、特に \(H_j \leq i-D\) の部分を工夫することで、先ほどの処理を以下のように言い換えることができます。

• \(dp=(0,0,\ldots,0), S=(-\infty,-\infty,\ldots,-\infty)\) と初期化する
• \(i=1,2,\ldots,N\) の順で以下を行う
  • \(D+1 \leq i\) の時、 \(S_{p_{i-D}} \leftarrow dp_{p_{i-D}}\) と更新する
  • \(l=\max(1,p_i-R),r=\min(N,p_i+R),M=\max(S_{l},S_{l+1},\ldots,S_{r})\) としたとき、\(dp_{p_i} \leftarrow \max(dp_{p_i},M+1)\) と更新する

この処理では \(S\) の区間最大値を求める部分がボトルネックとなっており、\(S\) に区間最大値セグメント木用いれば高速化できます。よって、この問題を時間計算量 \(\mathrm{O}(N \log N)\) で解くことができます。

実装例(C++)

#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;
int op(int a, int b) {
    return max(a, b);
}
int e() {
    return -1e9;
}
int main() {
    int n, d, r;
    cin >> n >> d >> r;
    vector<int> h(n);
    for (auto &e : h)
        cin >> e;
    for (auto &e : h)
        e--;
    vector<int> p(n);
    for (int i = 0; i < n; i++)
        p[h[i]] = i;
    vector<int> dp(n, 0);
    atcoder::segtree<int, op, e> seg(n);
    for (int i = 0; i < n; ++i) {
        if (i - d >= 0) {
            seg.set(p[i - d], dp[i - d]);
        }
        int mx = seg.prod(max(0, p[i] - r), min(n, p[i] + r + 1));
        dp[i] = max(dp[i], mx + 1);
    }
    cout << *max_element(dp.begin(), dp.end()) << '\n';
}