백준25414 구간 나누기

작성일 | In

문제 링크

  • http://icpc.me/25414

사용 알고리즘

  • DP

시간복잡도

  • $O(NK)$

풀이

$c(i, j) = \max\left{A_i, A_{i+1}, \cdots, C_j\right} - \min\left{A_i, A_{i+1}, \cdots, A_j\right}$가 monge라고 dnc opt를 사용하면 $O(KN \log N)$이라서 문제를 풀 수 없습니다.

구간에서 가장 큰 값을 정답에 더하고 가장 작은 값을 뺀다는 점을 잘 생각해 봅시다. 수열을 $K$개의 구간으로 분할하면 $N$개의 수 중 $K$개의 수를 정답에 더하고, $K$개의 수를 정답에서 빼게 됩니다. 그리고 선택된 원소들을 앞에서부터 차례대로 봤을 때, 더한 수의 개수와 뺀 수의 개수의 차이가 항상 1 이하로 유지된다는 점을 관찰할 수 있습니다.

반대로 생각해서, 수열의 원소에 +와 -를 $K$개씩 적당히 배치해서 그 결과를 최대화하는 문제를 생각해 봅시다. 이때 앞에서부터 누적된 +의 개수와 - 개수의 차이는 1 이하로 유지해야 합니다.
만약 결과가 최대가 되었다면, +와 -가 배치된 수는 각각 구간에서 가장 큰 값과 가장 작은 값이 될 것입니다. 그렇지 않다면 +/-를 최대/최솟값으로 이동시켜서 정답을 증가시킬 수 있기 때문입니다.

이 과정을 동적 계획법으로 처리해 봅시다. 점화식을 세 가지 정의할 것입니다.

  • $D(N, K, 0) = N$번째 원소까지 $K$개의 구간으로 나눴을 때의 최댓값
  • $D(N, K, 1) = N$번째 원소까지 $K$개의 구간으로 나눴고, 추가로 +를 하나 배치했을 때의 최댓값
  • $D(N, K, 2) = N$번째 원소까지 $K$개의 구간으로 나눴고, 추가로 -를 하나 배치했을 때의 최댓값

$O(NK)$에 모든 테이블을 채울 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, K, A[200001], D[200001][202][3];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K;
    for(int i=1; i<=N; i++) cin >> A[i];
    memset(D, 0xc0, sizeof D); D[0][0][0] = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<=K; j++){
            D[i+1][j][0] = max(D[i+1][j][0], D[i][j][0]);
            D[i+1][j+1][0] = max(D[i+1][j+1][0], D[i][j][0]);
            D[i+1][j][1] = max(D[i+1][j][1], D[i][j][0] + A[i+1]);
            D[i+1][j][2] = max(D[i+1][j][2], D[i][j][0] - A[i+1]);
            D[i+1][j+1][0] = max(D[i+1][j+1][0], D[i][j][1] - A[i+1]);
            D[i+1][j][1] = max(D[i+1][j][1], D[i][j][1]);
            D[i+1][j+1][0] = max(D[i+1][j+1][0], D[i][j][2] + A[i+1]);
            D[i+1][j][2] = max(D[i+1][j][2], D[i][j][2]);
        }
    }
    for(int i=1; i<=K; i++) cout << D[N][i][0] << "\n";
}