新規
編集
添付i番目の木に到達するのにかかるコストをC[i]、i番目の木の高さをH[i]とする。
C[i]を求める時、着目する必要があるのはC[i-K]～C[i-1]、H[i-K]～H[i-1]である。
C[i-K]～C[i-1]の最小値をAとする。
もし、C[k]==AかつH[k]>H[i]をみたすk(ただしi-K<=k<=i-1)が存在すると、C[i]=Aとなる。
そのようなkが存在しない場合、C[i]=A+1となる。なぜなら、C[l]!=Aなるl(ただしi-K<=l<=i-1)はすべてA+1以上となるため無視できるからである。
よって、スライド最小値を用いてk=i-K～i-1においての(C[k],-H[k])の最小値を求めると、各クエリごとO(N)、全体ではO(QN)で解くことができる。
