백준8984 막대기

작성일 | In

문제 링크

  • http://icpc.me/8984

문제 출처

  • 2013 KOI 중등부 3번, 고등부 2번

사용 알고리즘

  • DP

시간복잡도

  • $O(N \log N)$

풀이

조건을 만족하는 지그재그 선이 지나는 점들을 순서대로 보면, 윗줄과 아랫줄에 있는 점들의 x좌표가 각각 증가하는 형태입니다. 그러므로 DP를 생각해볼 수 있습니다.

윗줄의 $i$지점에서 끝나는 지그재그 선의 최대 길이를 $D_0(i)$, 아랫줄의 $i$지점에서 끝나는 지그재그 선의 최대 길이를 $D_1(i)$라고 정의합시다.
막대기를 정렬한 뒤 순서대로 보면서 $D_0(t) = \max(D_0(t), D_1(d) + len), D_1(d) = \max(D_1(d), D_0(t) + len)$과 같이 점화식을 계산해주면 됩니다. 이때 $len$은 막대기의 길이입니다.

전체 코드

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
#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())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

int n, l;
p v[101010];
vector<ll> compx, compy;
ll dp[2][101010];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> l; compx.reserve(n); compy.reserve(n);
    for(int i=1; i<=n; i++){
        cin >> v[i].x >> v[i].y;
        compx.push_back(v[i].x);
        compy.push_back(v[i].y);
    }
    sort(v+1, v+n+1);
    compress(compx); compress(compy);
    ll mx = 0;
    for(int i=1; i<=n; i++){
        int x = lower_bound(all(compx), v[i].x) - compx.begin();
        int y = lower_bound(all(compy), v[i].y) - compy.begin();
        ll a = dp[0][x], b = dp[1][y];
        ll dst = abs(v[i].x - v[i].y) + l;
        dp[0][x] = max(dp[0][x], b + dst);
        dp[1][y] = max(dp[1][y], a + dst);
        mx = max({mx, dp[0][x], dp[1][y]});
    }
    cout << mx;
}