累積和しながらDP
累積和しながら動的計画法
ABC179D
DPなどの最中に累積和の動的生成することがある
ABC179D
code:python
def accum_generation(N):
"""
>> accum_generation(10)
1, 0, 1, 1, 1, 2, 2, 3, 4, 5
"""
value = 0 * (N + 10)
accum = 0 * (N + 10)
value0 = 1
accum0 = 1
for pos in range(1, N):
ret = (accumpos - 2 - accumpos - 4)
valuepos = ret
accumpos = accumpos - 1 + ret
return value:N