티스토리 뷰

문제 풀이

[BOJ 4008] 특공대

RiKang 2017. 10. 31. 17:32

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] 가 성립하므로 같은 원리로 컨벡스 헐 트릭을 사용할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// code by RiKang, weeklyps.com
#include <stdio.h>
#include <algorithm>
#include <vector>
#define PII pair<long longlong 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<&& 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<&& 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;
}
 
cs


'문제 풀이' 카테고리의 다른 글

[BOJ 13518] 트리와 쿼리 9  (0) 2017.11.03
[CF 371 D] Animals and Puzzle  (0) 2017.10.31
[BOJ 4008] 특공대  (0) 2017.10.31
[CF 146 B] Let's Play Osu!  (0) 2017.10.31
[BOJ 2533] 사회망 서비스  (0) 2017.10.31
[BOJ 5060] 무글 맵스  (0) 2017.10.31