백준23299 화질 - 자동 (480p)

작성일 | In

문제 링크

  • https://icpc.me/23299

사용 알고리즘

  • 세그먼트 트리
  • DP

시간복잡도

  • $O(NK \log N)$

풀이

각 물건이 $[S_i, E_i]$ 시점에 존재할 때, 각 시점마다 냅색을 하는 문제입니다.

Offline Dynamic Connectivity와 비슷한 방식으로 문제를 해결합니다. 각 물건을 세그먼트 트리의 $O(\log N)$개의 정점에 넣습니다. 각 정점에서 DP를 한 다음, 그 DP 테이블을 자식 정점으로 넘겨주는 방식으로 정답을 구할 수 있습니다.

세그먼트 트리에는 $O(N \log N)$개의 물건이 존재하고, 각 물건마다 $O(K)$ 만큼의 시간이 필요하므로 전체 시간 복잡도는 $O(NK \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
#include <bits/stdc++.h>
using namespace std;
constexpr int SZ = 1 << 10;

int N, K, W[7], S[555], E[555], V[555][7];
vector<int> T[SZ<<1];
int D[SZ<<1][5050];
vector<int> C;
long long R;

void Add(int l, int r, int v, int node=1, int s=0, int e=SZ-1){
    if(r < s || e < l) return;
    if(l <= s && e <= r){ T[node].push_back(v); return; }
    int m = (s + e) / 2;
    Add(l, r, v, node<<1, s, m);
    Add(l, r, v, node<<1|1, m+1, e);
}

void Solve(int node=1, int s=0, int e=SZ-1){
    for(auto i : T[node]){
        for(int k=K; k>=0; k--){
            for(int j=1; j<=6; j++){
                if(k - W[j] >= 0) D[node][k] = max(D[node][k], D[node][k-W[j]] + V[i][j]);
            }
        }
    }
    if(s != e){
        int m = (s + e) / 2;
        memcpy(D[node<<1], D[node], sizeof D[node]);
        memcpy(D[node<<1|1], D[node], sizeof D[node]);
        Solve(node<<1, s, m); Solve(node<<1|1, m+1, e);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> K; C.reserve(N*2);
    for(int i=6; i>=1; i--) cin >> W[i];
    for(int i=1; i<=N; i++){
        cin >> S[i] >> E[i];
        for(int j=6; j>=1; j--) cin >> V[i][j];
    }
    for(int i=1; i<=N; i++) C.push_back(S[i]), C.push_back(E[i]);
    sort(C.begin(), C.end());
    for(int i=1; i<=N; i++){
        S[i] = lower_bound(C.begin(), C.end(), S[i]) - C.begin();
        E[i] = lower_bound(C.begin(), C.end(), E[i]) - C.begin();
    }
    for(int i=1; i<=N; i++) Add(S[i]+1, E[i], i);
    memset(D, 0xc0, sizeof D); D[1][0] = 0;
    Solve();
    for(int i=1; i<C.size(); i++) R += 1LL * *max_element(D[i|SZ], D[i|SZ]+K+1) * (C[i] - C[i-1]);
    cout << R;
}