백준 15678 / C++

https://www.acmicpc.net/problem/15678

15678번: 연세워터파크

 

[ 풀이 ] 

dp[j]=max(0, dp[k])+a[j] 이다. (단, k>=j-D , k<=j-1)  이 때, max(dp[k])를 구할때 세그트리로 O(logN)에 처리하자. 

구간 [j-D,j-1]에서 최댓값을 구하고 a[j]를 더해서 세그트리의 j번 인덱스에 dp값을 업데이트해주면 된다.

이전값의 최댓값이 음수인 경우 안뛰어도 되므로 max(0, dp[k])으로 써줬다. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, D, K[100001], tree[400004];

void upd(int node, int s, int e, int idx, ll v) {
	if (idx<s || idx>e) return;
	if (s == e) {
		tree[node] = v;
		return;
	}
	int m = (s + e) / 2;
	upd(2 * node, s, m, idx, v);
	upd(2 * node + 1, m + 1, e, idx, v);
	tree[node] = max(tree[2 * node], tree[2 * node + 1]);
}

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

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> D;
	for (int i = 1; i <= n; i++) cin >> K[i];
	ll ans = K[1];
	upd(1, 1, n, 1, K[1]);
	for (int i = 2; i <= n; i++) {
		ll temp = max(0LL, query(1, 1, n, max(1LL, i - D), i - 1)); // max(0, dp[k])
		ans = max(ans, K[i] + temp); // dp[i]
		upd(1, 1, n, i, K[i] + temp); // dp[i] update 
	}
	cout << ans << '\n';
}