まず、\(K=1\) の場合は茎を切る必要がないので答えは \(\displaystyle \sum_{i=1}^N H_i\) です。以降は \(K>1\) の場合を考えます。

条件は \(|i-j| < K\) ならば \(|H_i'-H_j'| \le D\) と言い換えることができます。この言い換え後の条件を連鎖的に用いることで、条件は任意の \(i,j\) に対し \(\displaystyle H_i' \le H_j + D\left\lceil\frac{|i-j|}{K-1} \right\rceil\) と同値であることも分かります。

また、この式から自明な上界として \(\displaystyle H_i' =\min_j \left( H_j + D\left\lceil\frac{|i-j|}{K-1} \right\rceil\right)\) が構成できます。そして、この解は構成可能であることもすぐ分かります。以降はこの \(H_i'\) を高速に計算する方法を考えます。

まず \(\displaystyle \min_j \left( H_j + D\left\lceil\frac{i-j}{K-1} \right\rceil\right)\) を \(\displaystyle A_i=\min_{1\le j\le i} \left( H_j + D\left\lceil\frac{j-i}{K-1} \right\rceil\right)\) と \(\displaystyle \min_{i \le j\le N} \left( H_j + D\left\lceil\frac{|i-j|}{K-1} \right\rceil\right)\) の \(2\) つに分解し、それぞれの値を計算することを考えます。

前者は \(\displaystyle\left\lceil\frac{i-j}{K-1} \right\rceil\) の繰り上がりを考えることで \(\displaystyle A_i = \min\left(H_i,A_{i-K+1}+D,\min_{1\le k\le K-1} (H_{i-k}+D)\right)\) という漸化式が求まります。これは SegTree を用いることで \(O(N\log N)\) 時間で計算することができます。\(B\) についても同様に計算できます。

以上を用いて \(H'\) を計算できるので、それらの総和も高速に計算することができます。

上記の方針の計算量は \(O(N\log N)\) ですが、スライド最小値を用いて \(O(N)\) 時間で計算することもできます。

実際には \(A\) と \(B\) を個別に計算せずにまとめて計算することができるので、下記の実装例では \(1\) つの SegTree でまとめて計算しています。

実装例(Python3)

from atcoder import segtree

n, k, d = map(int, input().split())
seg = segtree.SegTree(min, 10**9 + 2026, list(map(int, input().split())))
for i in range(n):
    seg.set(i, min(seg.get(i), seg.prod(max(0, i - k + 1), i) + d))
for i in reversed(range(n)):
    seg.set(i, min(seg.get(i), seg.prod(i, min(n, i + k)) + d))
print(sum(seg.get(i) for i in range(n)))