백준 4008 - 특공대 (C++)

문제

• 문제 링크

  
   BOJ 4008 - 특공대 
  

• 문제 요약

병사 $N$명의 전투력과 조정 전투력 등식 계수가 주어진다.
문제에 정의된 전투력 측정 방식을 따를 때, $n$명의 병사들에 대해 얻을 수 있는 최대 조정 전투력을 구해보자.

• 제한

TL : $1$ sec, ML : $64$ MB




$1 ≤ N ≤ 1,000,000$

$-5 ≤ a ≤ -1$

$|b| ≤ 10,000,000$

$|c| ≤ 30,000,000$

$1 ≤ xi ≤ 100$

알고리즘 분류

• 다이나믹 프로그래밍(dp)
• 볼록 껍질을 이용한 최적화(convex hull trick)

풀이

   CHT 대표 문제로 꼽히는 문제다. 물론 나도 CHT 태그를 타고 들어 왔지만 처음 내 반응은 "이게 왜 CHT?" 였다.

우선 연속 부분 수열 합을 고려해야 하므로 빠른 계산을 위해 입력 받음과 동시에 누적 합 배열로 바꿔주자. ( $A[]$ )
그리고 다음과 같이 정의를 내려보자.

$dp[i]$ : $1$ ~ $i$의 병사들로 구성할 수 있는 최대 조정 전투력.

나이브한 풀이를 생각해보자.
문제에 정의된 함수 $g(x) = a * x^2 + b * x + c$ 라 하고 초기값 $dp[i] = g(A[i])$ 일 때
$1 ≤ j < i$ 에서 $dp[i] = max(dp[i], dp[j] + g(A[i] - A[j]))$ 로 정리할 수 있다.

모든 $i$에 대한 $j$를 돌아보면 $O(N^2)$으로 문제를 해결할 수 있지만, 제한을 보면 어림도 없다.
우항을 전개하여 좀 더 세부적으로 식을 들여다보자.

---

$dp[j] + g(A[i] - A[j])$
$= dp[j] + a * (A[i]-A[j])^2 + b * (A[i]-A[j]) + c$
$= dp[j] + a * A[i]^2 - 2 * a * A[i] * A[j] + a * A[j]^2 + b * A[i] - b * A[j] + c$

위에서 정의한 $j, i$의 범위 관계에 따라 $A[i] = x$로 두고 $Δj$의 영향을 보기 위해 $j$가 포함된 항들을 앞으로 빼자.

$f(x) = -2 * a * A[j] * x + a * A[j]^2 - b * A[j] + dp[j] + a * A[i]^2 + b * A[i] + c$

$Δj$와 무관한 상수항을 제외하면

$f(x) = -2 * a * A[j] * x + a * A[j]^2- b * A[j] + dp[j]$

따라서 기울기 $-2 * a * A[j]$, $y$절편 $a * A[j]^2- b * A[j] + dp[j]$ 을 갖는 직선의 방정식의 꼴로 정리할 수 있다. ( $f(x) = ax + b$ )

---

결국 이 문제는 $1 ≤ i ≤ n$ 인 $i$에 대해 $max(f(i))$를 찾는 것이 된다.
하지만 위에서 말했듯 $i$마다 $1 ≤ j < i$인 모든 $j$에 대해 돌아볼 순 없는 노릇이다.
다음을 보자.

• $A[]$는 '누적 합' 배열이다.
• $n_i$는 $1 ≤ n_i ≤ 100$를 만족한다.
• 즉, $A[]$는 단조 증가한다.
• $f(x)$의 기울기 $-2 * a * A[j]$ 에서 $A[]$가 단조 증가 하고 $-2 * a(-5 ≤ a ≤ -1)$ 가 양수 이므로 $f(x)$의 기울기 역시 단조 증가한다.

따라서 기울기에 이분 탐색을 적용해 $O(N logN)$으로 문제를 해결할 수 있다.

전체 코드

#include<bits/stdc++.h>
#define ll long long
#define N 1000001
using namespace std;
 
struct S
{
    ll p, q;
    double d;
    bool operator<(int x) { return d < x; }
}ln[N];
ll n, u, a, b, c, i, A[N], dp[N];
 
ll g(ll x) { return a * A[x] * A[x] + b * A[x] + c; }
ll y(ll x) { return a * A[x] * A[x] - b * A[x] + dp[x]; };
double f(S& l, S& r) { return (r.q - l.q) / (l.p - r.p); }
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> a >> b >> c;
    for (i = 1; i <= n; i++)
        cin >> A[i], A[i] += A[i - 1];
    for (i = 1; i <= n; i++)
    {
        S t({ -2 * a * A[i - 1], y(i - 1), 0 });
        while (u)
        {
            t.d = f(t, ln[u - 1]);
            if (t.d > ln[u - 1].d) break;
            u--;
        }
        ln[u++] = t;
        ll j = lower_bound(ln, ln + u, A[i]) - ln - 1;
        dp[i] = ln[j].p * A[i] + ln[j].q + g(i);
    }
    cout << dp[n];
}

comment

끝