abc040_c
DP Aで見た問題。同じ解き方をしても面白くないので「動的計画法なのに配列を確保しない」を試して列の長さが短い時にREした
pythondef solve(N, XS):
if N == 1:
return 0
a = abs(XS[1] - XS[0])
if N == 2:
return a
b = abs(XS[2] - XS[0])
if N == 3:
return b
for i in range(3, N):
v = min(
a + abs(XS[i - 2] - XS[i]),
b + abs(XS[i - 1] - XS[i]),
)
a = b
b = v
return vRelated Pages
- →動的計画法×DP A×dp_b×dp_c×dp_d×dp_e×dp_f×dp_g×dp_h×dp_i×dp_j×dp_k×dp_l×dp_m×dp_n×dp_o×dp_p×dp_q×dp_r×dp_s×dp_t×dp_u×dp_v×dp_w×dp_x×dp_y×dp_z→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]