연세워터파크

문제 링크

발상

어느 지점에서든 점프를 중지하고 현재 점수로 끝낼 수 있다 = 모든 지점에서 최댓값을 갱신한다. 어느 지점에서든 시작할 수 있다 = 현재 지점에서 고를 수 있는 값들이 전부 음수일 경우, 선택하지 모두 선택하지 않고 현재 징검 다리의 점수만을 취할 수 있다. 로 치환해 읽을 수 있다. 풀이의 편의를 위해 왼쪽 첫번째 징검다리에서 시작해 오른쪽 마지막 징점다리까지 점프한다고 가정하자. 현재 징검다리 인덱스 $i$로 도착할 수 있는 징검다리 인덱스 범위는 $(i-k)\sim (i-1)$이다. (해당 범위의 최적값 중 최대 점수) + (현재 징검다리 점수) 가 현재 징검다리를 밟으면서 얻을 수 있는 최적값이 된다. 단, 처음에 써놨듯이 범위 내 값들이 전부 음수인 경우, 굳이 취할 이유가 없으므로 현재 징검다리에서 시작하는 예외적 선택지만 추가로 고려하면 된다.

점화식

$$\{\begin{array}{l}{N}_i=\text{i위치까지의 최적값}\\ A_i=\text{i위치 징검다리의 점수}\end{array}$$ $$\begin{array}{rl}{P}_i& =\underset{p=(i-k)\to (i-1)}{\max }(N_p)\\ N_i& =\{\begin{array}{ll}{P}_i& \text{if Pi>0}\\ 0& \text{else}\end{array}+A_i\end{array}$$

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
using ll = long long;
struct node {
    ll i, v;
};
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, k; cin >> n >> k; vector<ll> arr(n + 1), dp(n + 1); deque<node> dq;
    ll s = 0;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];        
        s += arr[i];
    }
    ll mx = -1e15;    
    for (int i = 1; i <= n; i++) {
        while (!dq.empty() && i - dq.front().i > k) dq.pop_front();
        ll p = dq.empty() ? 0 : dq.front().v;        
        dp[i] = (p > 0 ? p : 0) + arr[i]; // 이전 배열 최적값이 음수인 경우 고려할 가치가 없음 ( 현재 징검다리에서 시작하는게 더 나은 경우 ) 
        while (!dq.empty() && dq.back().v < dp[i]) dq.pop_back();
        dq.push_back({ i, dp[i] });
        mx = mx > dp[i] ? mx : dp[i];
    }
    cout << mx;
    return 0;
}