백준[15678] 연세워터파크

문제 설명

문제 링크

http://icpc.me/15678

15678번: 연세워터파크

풀이

세그먼트 트리로 dp최적화를 하는 문제다.

dp[i] = max(dp[i], max(dp[i - k]) + arr[i]) (1 <= k <= d)로 정의할 수 있다.

이때 max(dp[i - k])를 구하는 과정을 O(N)에 한다면 시간 초과가 발생한다.

그렇기 때문에 이 부분을 O(logN)만에 한다면 O(NlogN)에 문제를 풀 수 있다. 이 과정에서 세그먼트 트리를 이용하면 된다.

코드

#include <cstdio>
#include <algorithm>
#define mid ((s + e) >> 1)
using namespace std;
using ll = long long;

const int N = 1e5 + 5;

ll dp[N];
ll tree[4 * N];

ll query(int node, int s, int e, int qs, int qe) {
    if (qe < s || e < qs) return -1e9;
    if (qs <= s && e <= qe) return tree[node];
    return max(query(2 * node, s, mid, qs, qe), query(2 * node + 1, mid + 1, e, qs, qe));
}

void update(int node, int s, int e, int idx, ll k) {
    if (idx < s || e < idx) return;
    if (s == e) {
        tree[node] = k;
        return;
    }
    update(2 * node, s, mid, idx, k);
    update(2 * node + 1, mid + 1, e, idx, k);
    tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}

int main() {
    int n, d; scanf("%d %d", &n, &d);
    for (int i = 0; i < n; i++) scanf("%lld",dp + i);
    for (int i = 0; i < n; i++) {
        dp[i] = max(dp[i], query(1, 0, N, max(0, i - d), i - 1) + dp[i]);
        update(1, 0, N, i, dp[i]);
    }
    printf("%lld", *max_element(dp, dp + n));
}