백준19672 Feast

작성일 | In

문제 링크

  • http://icpc.me/19672

사용 알고리즘

  • Aliens Trick

시간복잡도

  • $O(N \log X)$

풀이

구간을 하나 더 선택할 때마다 얻는 이득이 점점 감소한다는 것($K$에 대한 정답이 볼록하다는 것)은 직관적으로 알 수 있습니다. 그러므로 Aliens Trick을 생각해볼 수 있습니다. $K$ 조건을 없애고, 구간을 한 개 선택할 때마다 $c$만큼 패널티가 감소하는 문제를 풀어봅시다.

$D(i, 0)$을 $1\cdots i$번째 원소만 고려했을 때, $i$번째 원소는 선택한 구간에 포함하지 않은 최댓값, $D(i, 1)$는 $i$번째 원소를 포함한 최댓값이라고 정의합시다. 상태 전이는 다음과 같습니다.

  • $D(i, 0) \leftarrow \max\lbrace D(i-1, 0), D(i-1, 1) \rbrace$
  • $D(i, 1) \leftarrow \max\lbrace D(i-1, 0) + A_i - c, D(i-1, 1) + A_i \rbrace$

크기가 0인 구간도 선택할 수 있으므로, 최댓값이 같다면 선택한 구간의 개수는 가장 작은 값을 저장하면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;

struct DP{
    ll v, c;
    DP() : DP(0, 0) {}
    DP(ll v, ll c) : v(v), c(c) {}
    bool operator < (const DP &t) const { return v != t.v ? v < t.v : c > t.c; }
    DP operator + (const DP &t) const { return {v + t.v, c + t.c}; }
};

int N, K;
ll A[303030];
DP D[303030][2];

int Check(ll c){
    D[0][0] = {0, 0};
    D[0][1] = {-INF, 0};
    for(int i=1; i<=N; i++){
        D[i][0] = max(D[i-1][0], D[i-1][1]);
        D[i][1] = max(D[i-1][0] + DP(A[i] - c, 1), D[i-1][1] + DP(A[i], 0));
    }
    return max(D[N][0], D[N][1]).c;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K;
    for(int i=1; i<=N; i++) cin >> A[i];
    ll l = 0, r = INF;
    while(l < r){
        ll m = l + r >> 1;
        if(Check(m) <= K) r = m;
        else l = m + 1;
    }
    Check(r);
    cout << max(D[N][0], D[N][1]).v + r * K;
}