APIO 2010 1번 특공대(Commando)

N개의 숫자가 있다. 이를 연속된 구간으로 나눠서, 각 구간의 수의 합을 s라고 했을 때 as²+bs+c 의 값의 합(모든 구간에서 저 값을 구한 후 다 더함)을 최대화하는 문제이다. (a, b, c가 주어짐)

=> maximize( a(s₁²+ s₂²+…s_k²)+b(Σ)+c×k ).

여기서 b항의 값은 항상 일정하기 때문에 a와 c값만 중요하다.

=> maximize( a(s₁²+ s₂²+…s_k²)+c×k ).

dp[i] : a[i]까지의 숫자만 있다고 할 때 저 값의 최댓값. i는 1-based.

i를 j까지 묶는다고 하자.

1≤j≤i 이다.

dp[i] = maximize( dp[j-1] + a*(sum[i]-sum[j-1])^2 + c ) for j.

=

a*(sum[i]^2)+maximize(

dp[j-1]

-2*a*sum[i]*sum[j-1]

+a*(sum[j-1]^2)+c

) for j

p[i] = -2*a*sum[i], q[i]=dp[i]+c+a*(sum[i]^2) 라고 하자.

p is increasing.

dp[i] = a*sum[i]^2 + maximize(p[j-1]*sum[i] + q[j-1]) for j

x coordinate is increasing.

convex hull trick