[백준 15678] 연세워터파크

문제

www.acmicpc.net/problem/15678

 

알고리즘

세그먼트 트리 + DP

 

풀이

$N$개의 발판이 주어지고 각 발판마다 점수가 있을 때, 얻을 수 있는 점수의 최댓값을 묻고 있습니다.

 

흔한 다이나믹프로그래밍 주제입니다. $dp[i]$를 $i$번째 발판까지 밟았을 때, 얻을 수 있는 최댓값이라고 하겠습니다.

각 i번째 발판마다 자신의 최댓값을 구하기 위해서는 $dp[i-D]$ ~ $dp[i-1]$ 사이의 최댓값을 얻으면 $dp[i]$를 구할 수 있습니다. 요구하는 시간 복잡도는 $O(N^2)$ 이므로 시간초과입니다.

 

눈에 띠는 것은 구간값 중 최대값을 요구하고 있습니다. 반복문을 통해 선형시간에 해결하는 것 말고도 세그먼트 트리를 활용하면 구간값을 $O(logN)$에 구할 수 있습니다.

 

입력을 받으며 [i~D,i-1] 사이의 최댓값에 $val[i]$를 더해 세그먼트 트리를 갱신합시다. 구간의 최댓값을 $v$라 한다면 마지막에 max(v,0)을 통해 $v$구간을 선택하지 않고 $val[i]$만 선택하는 것 또한 처리하도록 합시다. 시간복잡도는$O(NlogN)$ 입니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;
#define int long long
int n, d;

vector<int> seg;
int query(int node, int nl, int nr, int ql, int qr) {
    if (qr < nl || nr < ql) return INT_MIN;
    if (ql <= nl && nr <= qr) return seg[node];
    int mid = (nl + nr) >> 1;
    return max(query(node << 1, nl, mid, ql, qr), query(node << 1 | 1, mid + 1, nr, ql, qr));
}

void update(int node, int nl, int nr, int idx, int val) {
    if (idx < nl || nr < idx) return;
    if (nl == nr) {
        seg[node] = val;
    }
    else {
        int mid = (nl + nr) / 2;
        if(nl<=idx&&idx<=mid) update(node << 1, nl, mid, idx, val);
        if(mid+1<=idx&&idx<=nr) update(node << 1 | 1, mid + 1, nr, idx, val);
        seg[node] = max(seg[node << 1], seg[node << 1 | 1]);
    }
}

signed main() {
    FAST;
    cin >> n >> d;
    
    int S = pow(2, ceil(log2(n)));
    S = S << 1;
    seg.resize(S);
    rep(i, n) {
        cin >> seg[i + n];
        int v = max(0LL,query(1, 0, n - 1, max(0LL, i - d), max(0LL, i - 1))) + seg[i+n];
        update(1, 0, n - 1, i, v);
    }

    cout << query(1, 0, n - 1, 0, n - 1);

    return 0;
}