yukicoder 1353 Limited Sequence
DPということは自明. しかし愚直にやると$ dp_{i,j,k} := 条件を満たす数列のうち長さ$ iの数列であって要素の総和が$ j, 最後の要素が$ kであるようなものの数 となり, これは時間計算量・空間計算量ともに$ O(NR^2)となって間に合わない.
ここでDPで持つ情報を削減することを考える. 具体的には, $ dp_{i,j} := 条件を満たす数列のうち要素の総和が$ i, 最後の要素が$ jであるようなものの数と定義してみる. すると空間計算量は$ O(NR)に削減できる. 時間計算量について削減することを考える. まず愚直な遷移を考えると, 累積和で高速化できるような形をしているということがわかる. また, コードの$ kの部分は$ O(R \log R)になっていることがわかる. よってこの問題を$ O(NR \log R)で解くことができた.