백준10841 매트

작성일 | In

문제 링크

  • http://icpc.me/10841

문제 출처

  • 2015 KOI 고등부 3번

사용 알고리즘

  • DP
  • 스위핑

시간복잡도

  • $O(N^2)$

풀이

DP 문제라는 것은 쉽게 알 수 있지만, 점화식을 어떻게 정의해야할지 잘 보이지 않는 문제입니다.

데이터를 정렬하고 좌표압축해서 손해볼 것은 없으니, 일단 입력으로 주어진 매트 조각들을 $(L, R)$ 오름차순으로 정렬하고 $L, R$은 좌표 압축을 해줍시다. 서로 다른 $L, R$ 값은 최대 $2N$개 존재하므로 $L, R$을 $2N$ 이하의 자연수로 표현할 수 있습니다.

x좌표가 $j$인 지점까지만 사용하고, 마지막으로 사용한 매트가 $i$번째 매트일 때 얻을 수 있는 이익의 최댓값을 $D(i, j)$라고 정의합시다.

DP 상태 전이는 다음과 같습니다. 설명의 편의를 위해 $i$번째 매트의 $L$값을 $L(i)$, $R$값을 $R(i)$, 그 매트의 가격을 $V(i)$라고 합시다.

  • $D(i, j) \leftarrow D(i, j-1)$
  • $i$번째 매트와 겹치지 않고, $L(k) \geq j$인 매트 $k$에 대해
    • $R(i) \leq R(k)$이면 $D(k, R(i)) \leftarrow D(i, j) + V(k)$
    • $R(i) \geq R(k)$이면 $D(i, R(k)) \leftarrow D(i, j) + V(k)$

$D(i, j)$를 계산한 뒤 $D(i, j+1)$로 보내줄 수 있으므로, $D(i, j)$를 계산할 때는 $L(k) \geq j$가 아닌 $L(k) = j$인 $k$만 봐도 충분합니다.
각각의 $i$에 대해, $D(i, \ast)$를 계산할 때 고려하는 $j$의 개수가 최대 $2N$개, $k$의 개수가 최대 $N$개이므로 $O(N^2)$에 점화식을 계산할 수 있습니다.

전체 코드

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
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#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;

struct Rectangle{
    int p, s, e, h, v;
    Rectangle() = default;
    Rectangle(int p, int s, int e, int h, int v) : p(p), s(s), e(e), h(h), v(v) {}
    bool operator < (const Rectangle &r) const { return tie(s, e) < tie(r.s, r.e); }
    friend istream& operator >> (istream &in, Rectangle &r){ in >> r.p >> r.s >> r.e >> r.h >> r.v; return in; }
};

int N, M, W, D[3030][6060], mx;
Rectangle A[3030];
vector<int> C, G[6060];

int Cross(const Rectangle &r1, const Rectangle &r2){
    if(r1.p != r2.p && r1.h + r2.h <= W) return false;
    return !(r1.e <= r2.s || r2.e <= r1.s);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> W; M = N + N;
    for(int i=1; i<=N; i++) cin >> A[i], C.push_back(A[i].s), C.push_back(A[i].e);
    sort(A+1, A+N+1); compress(C);
    for(int i=1; i<=N; i++) A[i].s = IDX(C, A[i].s) + 1, A[i].e = IDX(C, A[i].e) + 1, G[A[i].s].push_back(i);

    for(int i=1; i<=N; i++){
        D[i][0] = A[i].v;
        for(int j=1; j<=M; j++){
            D[i][j] = max(D[i][j], D[i][j-1]);
            for(const auto &k : G[j]){
                if(Cross(A[i], A[k])) continue;
                if(A[i].e < A[k].e) D[k][A[i].e] = max(D[k][A[i].e], D[i][j] + A[k].v);
                else                D[i][A[k].e] = max(D[i][A[k].e], D[i][j] + A[k].v); /* A[k].e <= A[i].e */
            }
        }
        mx = max(mx, D[i][M]);
    }
    cout << mx;
}