1/3 PKU

2313 Sequence

数列A(1),A(2),…,A(N)が与えられるから、
V = (|A(1) – B(1)| + |A(2) – B(2)| + ... + |A(N) – B(N)|) + (|B(1) – B(2)| + |B(2) – B(3)| + ... +|B(N-1) – B(N)|)
を最小化するB(1),…,B(N)について、Vを求めよ。

• 10000<=A(i)<=10000だから、-10000<=B(i)<=10000。最後のB(i)の値でDP。

どうやらgreedyのような解法もあるらしいけど知らない