백준 10067번: 수열 나누기 [C++]

작성일 | In
다이아몬드 IV 다이아몬드 IV

문제

수열 나누기

풀이

구간 $[1, n]$을 $k + 1$개의 구간으로 나누었을 때 $i$번째 구간의 합을 $s_i$라 합시다. 이때 $i - 1$번째 구간과 $i$번째 구간 사이를 나누는 경우 점수에는 $s_1s_i + s_1s_{i + 1} + s_1s_{i + 2} + \dots + s_2s_i + s_2s_{i + 1} + \dots$가 더해지는데, 이는 $[1, i - 1]$에서 하나를 뽑고 $[i, k + 1]$에서 하나를 뽑아 $s$를 곱한 값을 모두 더한 것과 같습니다. 따라서 $k$번 나누고 나서 얻은 점수는 결국 모든 $k + 1$개에서 두개를 뽑아 서로 곱한 값을 모두 더한 것과 같게 됩니다.

따라서 어떤 순서로 나누든 결과가 같다면 점수도 같음을 알 수 있습니다.

$dp[t][i]$를 구간 $[1, i]$를 $t + 1$개의 구간으로 나눌 때 얻을 수 있는 최대의 점수로 정의합시다. 그렇다면 아래의 점화식으로 $dp$를 구할 수 있습니다.

\[dp[t][i] = \max(dp[t - 1][j - 1] + (S_i - S_{j - 1})S_{j - 1})\]

메모리 제한이 그렇게 널널하지 않으므로 아래 두 풀이 모두 토글링 기법을 사용해서 메모리를 절약했습니다.

DnC

$S_{j - 1}$을 왼쪽 구간의 합, $(S_i - S_{j - 1})$을 오른쪽 구간의 합이라 부르겠습니다.

$dp[t][i] = dp[t - 1][j - 1] + (S_i - S_{j - 1})S_{j - 1}$을 만족하는 $j$를 $opt$라 합시다.

$t$가 같다면 $i$가 커질수록 $dp[t][i]$의 값도 증가합니다.

두 수의 합이 일정할 때 두 수의 곱은 두 수의 차가 작을수록 커집니다.

따라서 $opt$는 왼쪽 구간의 합과 오른쪽 구간의 합의 차가 가장 작도록 하는 $j$보다 크거나 같아야 합니다. 그렇지 않은 경우 $opt$가 증가하면 $dp$값과 두 구간의 곱 모두 증가하므로 $opt$가 최적이 아님을 알 수 있습니다.

$i$를 증가시켜 봅시다. 값은 그대로인데 두 구간의 곱이 증가합니다. 이때 값이 늘어나는 구간은 오른쪽 구간이므로 왼쪽 구간의 합이 클 수록 두 구간의 곱이 더 많이 커집니다. 따라서 $opt$는 증가합니다.

$i$를 감소시켜 봅시다. $dp$값은 그대로인데 두 구간의 곱이 감소합니다. 아까와 마찬가지로 왼쪽 구간의 합이 작을수록 두 구간의 곱도 덜 작아집니다. 따라서 $opt$는 감소합니다.

따라서 $i < i’$인 경우 $opt_i \le opt_i’$이므로 분할 정복을 사용한 최적화를 통해 시간 복잡도 $\mathcal{O}(kn\log n)$에 해결할 수 있습니다.

코드

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
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(ignore) ((void)0)
#endif
using namespace std;

using ll = long long;

ll a[101010];

ll dp[2][101010];
int opt[222][101010];

ll cost(int l, int r) {
    return (a[r] - a[l - 1]) * a[l - 1];
}

void dnc(int t, int s, int e, int l, int r) {
    if (s > e)
        return;

    int m = (s + e) >> 1;

    dp[t & 1][m] = dp[~t & 1][l - 1] + cost(l, m);
    opt[t][m] = l;
    for (int i = l + 1; i <= min(m, r); i++) {
        ll v = dp[~t & 1][i - 1] + cost(i, m);
        if (v >= dp[t & 1][m]) {
            dp[t & 1][m] = v;
            opt[t][m] = i;
        }
    }

    dnc(t, s, m - 1, l, opt[t][m]);
    dnc(t, m + 1, e, opt[t][m], r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1];
    }

    for (int t = 1; t <= k; t++)
        dnc(t, 1, n, 1, n);

    cout << dp[k & 1][n] << '\n';

    int prev = n;
    for (int i = k; i >= 1; i--)
        cout << (prev = opt[i][prev] - 1) << ' ';

    return 0;
}

CHT

점화식을 약간 변형하면 $dp[t][i] = \max(S_{j - 1}S_i - S_{j - 1}^2 + dp[t - 1][j - 1])$ 이 됩니다. 이는 변수가 $S_i$이고 기울기가 $S_{j - 1}$, y 절편이 $-S_{j - 1}^2 + dp[t - 1][j - 1]$인 직선으로 볼 수 있습니다.

기울기와 변수 모두 단조증가하므로 단조 큐를 이용한 볼록 껍질을 이용한 최적화로 시간 복잡도 $\mathcal{O}(kn)$에 해결할 수 있습니다.

점화식에서 $j \le i$ 이어야 하므로 $i \le n - (k - t)$인 $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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(ignore) ((void)0)
#endif
using namespace std;

using ll = long long;
using ld = long double;

struct Line {
    int idx;
    ll slope, yinter;
    ld start;

    Line(int _idx, ll _slope, ll _yinter)
        : idx(_idx), slope(_slope), yinter(_yinter), start(-INFINITY) {}

    ld getIntersection(const Line& l) const {
        return (ld)(l.yinter - yinter) / (slope - l.slope);
    }
};

ll sum[101010];
int opt[222][101010];
deque<Line> lines[2];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        cin >> sum[i];
        sum[i] += sum[i - 1];
    }

    lines[1].emplace_back(0, 0, 0);
    for (int t = 0; t <= k; t++) {
        lines[t & 1].clear();

        for (int i = 1; i <= n - (k - t); i++) {
            Line l = lines[~t & 1].front();
            lines[~t & 1].pop_front();

            while (not lines[~t & 1].empty() and
                   lines[~t & 1].front().start <= sum[i]) {
                l = lines[~t & 1].front();
                lines[~t & 1].pop_front();
            }

            lines[~t & 1].push_front(l);

            opt[t][i] = l.idx;

            ll dp = sum[i] * l.slope + l.yinter;

            Line newLine(i, sum[i], dp - sum[i] * sum[i]);
            while (not lines[t & 1].empty()) {
                Line back = lines[t & 1].back();

                if (newLine.slope == back.slope) {
                    newLine.yinter = max(newLine.yinter, back.yinter);
                    lines[t & 1].pop_back();
                    continue;
                }

                newLine.start = newLine.getIntersection(back);
                if (newLine.start <= back.start)
                    lines[t & 1].pop_back();
                else
                    break;
            }
            lines[t & 1].push_back(newLine);
        }
    }

    Line l = lines[~k & 1].front();
    cout << sum[n] * l.slope + l.yinter << '\n';

    int prev = n;
    for (int i = k; i >= 1; i--) {
        prev = opt[i][prev];
        cout << prev << ' ';
    }

    return 0;
}

백준 10067번: 수열 나누기 [C++]