[BOJ 4008] 특공대

DP[i] = 1 ~ i 병사들로 얻을 수 있는 조정된 전투력의 최댓값

위와 같은 간단한 DP를 구하면 된다.

SUM[i] = X[1]+X[2]+...+X[i] 로 미리 sum 배열을 구해 놓으면

SUM[i] - SUM[j] = X[j+1]+X[j+2]+...+X[i] 가 성립하므로 아래와 같이 DP[i]를 구할 수 있다.

이 식을 전개하여 컨벡스 헐 트릭을 사용할 수 있게 i 와 관련된 함수( = SUM[i]가 곱해진 항) , j와 관련된 함수, 상수를 나누면

위와 같이 된다.

이제 A[i] = SUM[i],   B[j] = -2*a*sum[j]+b, C[j] = DP[j]-b*sum[j]+a*sum[j]^2, D[i] = a*sum[i]^2+c 로 대응시킬 수 있다.

min 함수가 아닌 max 함수이지만,

a<0 && sum[i-1]<=sum[i] 의 조건에 의해 B[i-1] <= B[i] 가 성립하므로 같은 원리로 컨벡스 헐 트릭을 사용할 수 있다.

// code by RiKang, weeklyps.com
#include <stdio.h>
#include <algorithm>
#include <vector>
#define PII pair<long long, long long>
 
using namespace std;
 
const int N=1000000;
 
struct line{  // y = a*x + b
    long long a,b;
};
 
struct convexhull_trick{
    int s=0,e=0;
    int idx[N+5];
    line deq[N+5];
    double cross(int a, int b) {
        return 1.0 * (deq[a].b - deq[b].b) / (deq[b].a - deq[a].a);
    }
    void insert(line v,int line_idx){
        deq[e] = v;
        idx[e] = line_idx;
        while(s+1<e && cross(e - 2, e - 1) > cross(e - 1, e)){
            deq[e-1] = deq[e];
            idx[e-1] = idx[e];
            e--;
        }
        e++;
    }
    PII query(long long x){  // query가 증가수열일 경우
        while(s+1<e && deq[s+1].b - deq[s].b >= x * (deq[s].a - deq[s+1].a))
            s++;
        return PII(deq[s].a*x+deq[s].b,idx[s]);
    }
    PII query2(long long x){ // 일반 query
        int l = 0, r = e - 1;
        while (l != r) {
            int m = (l + r) / 2;
            if (cross(m, m + 1) <= x) l = m + 1;
            else r = m;
        }
        return PII(deq[l].a*x+deq[l].b,idx[l]);
    }
    void clear(){s = e = 0;}
}cht;
 
int n;
long long a,b,c;
long long x[N+5];
long long sum[N+5];
long long dp[N+5];
 
int main(){
    cht.clear();
    scanf("%d",&n);
    scanf("%lld %lld %lld",&a,&b,&c);
    for(int i=1; i<=n; i++){
        scanf("%lld",&x[i]);
        sum[i] = sum[i-1]+x[i];
    }
    line ins;
    ins.a = b;
    ins.b = 0;
    cht.insert(ins,0);
    for(int i=1; i<=n; i++){
        dp[i] = c+a*sum[i]*sum[i]+cht.query2(sum[i]).first;
        ins.a = -2*a*sum[i]+b;
        ins.b = dp[i]-b*sum[i]+a*sum[i]*sum[i];
        cht.insert(ins,i);
    }
    printf("%lld",dp[n]);
    return 0;
}