[C++] 4008번 특공대 - DP, 볼록 껍질을 이용한 최적화, 누적 합

4008번 특공대

1. 문제

• 1번부터 n번까지 번호가 붙여진 병사가 있다. 지휘관은 번호가 연속하도록 여러 특공대를 나눈다. 각 병사의 전투력은 $x_i$이며 이들로 구성된 특공대의 각 병사 전투력 합이 x라고 할 때 이 특공대의 전투력은 $a{x}^2+bx+c$이다. $(a<0)$. 각 특공대의 전투력의 합의 최댓값을 구하시오.

<입력>

• -1-   전체 병사 수 $n(1\le n\le 1,000,000)$
• -1-   세 정수 a, b, c $(-5\le a\le -1,\left|b\right|\le 10,000,000,\left|c\right|\le 30,000,000)$
• -1-   $x_1,x_2,...,x_n(1\le x_i\le 100)$

<출력>

• -1-   각 특공대의 전투력 합의 최댓값

2. 재정의

• X

3. 해결 방법

• 0번째 부터 i번째 병사의 전투력의 합을 S[i]라고 하자. 이때 i번까지의 병사들로 구성되었을 때 전투력의 합의 최댓값을 dp(i)라고 하자. 그러면 dp(i)를 아래와 같이 나타낼 수 있다.

• a(j)는 S[j]가 누적 합으로 j가 커질수록 증가하기에 볼록 껍질을 이용한 최적화로 dp값을 O(nlgn)으로 구할 수 있다.

4. 실수한 점, 개선할 점

• i가 커짐에 따라 S[i], 즉 x가 커지므로 굳이 적합한 직선을 찾기 위해 이분 탐색을 할 필요는 없다.
• 교점을 구할 때 double형임을 조심하자.

 

<코드>

#include <iostream>

using namespace std;

typedef long long int ll;
typedef long double ld;

const int MAX_N = 1000000;

// <문제>
// 전체 병사 수 N, 계수 a,b,c
int N, a, b, c;
// 병사 전투력 X[i]
int X[MAX_N];

// 누적합 S[i]
ll S[MAX_N];
// dp[i]
ll dp[MAX_N];

// 직선의 방정식
// f(x) = ax + b, x >= s;
struct LinearFunc { 
    ll a, b;
    ld s;
    LinearFunc(): LinearFunc(1, 0){}
    LinearFunc(ll _a, ll _b) : a(_a), b(_b), s(0) {}
};

// 두 직선의 교점
inline ld cross(LinearFunc &f, LinearFunc &g) {
    return 1.0 * (g.b - f.b)/(f.a - g.a);
}

LinearFunc f[MAX_N];

void input() {
    cin >> N;
    cin >> a >> b >> c;
    
    cin >> X[0]; S[0] = X[0];
    for(int i=1; i<N; i++) {
        cin >> X[i];
        S[i] = S[i-1] + X[i];
    }
}

void solve() {
    int top = 0;
    
    dp[0] = a*X[0]*X[0] + b*X[0] + c;
    for(int i=1; i<N; i++) {
        ll _a = -2*a*S[i-1];
        ll _b = a*S[i-1]*S[i-1] - b*S[i-1] + dp[i-1];
        LinearFunc g(_a, _b);
        
        while(top > 0) {
            g.s = cross(f[top-1], g);
            if(g.s > f[top-1].s)
                break;
            --top;
        }
        f[top++] = g;
        
        ll x = S[i];
        int fpos = top-1;
        if(x < f[top-1].s) {
            int lo = 0, hi = top - 1;
            while(lo + 1 < hi) {
                int mid = (lo+hi)/2;
                (x < f[mid].s ? hi : lo) = mid;
            }
            fpos = lo;
        }
        dp[i] = max(f[fpos].a * x + f[fpos].b, (ll)0) + a*S[i]*S[i] + b*S[i] + c;
    }
    
    cout << dp[N-1];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    solve();
    
    return 0;
}

 

 

<문제 바로가기>

https://www.acmicpc.net/problem/4008

4008번: 특공대

 

<컨벡스 헐 트릭(Convex Hull Trick)>

https://blog.naver.com/PostView.nhn?blogId=kks227&logNo=221418495037&proxyReferer=https:%2F%2Fwww.google.com%2F 

컨벡스 헐 트릭(Convex Hull Trick)

 

※ 궁금한 것 질문 남겨주시면 답변드리겠습니다. 좋아요 눌러주시고 편하게 질문해 주세요.