백준 15678 - 연세워터파크

www.acmicpc.net/problem/15678

 

단조 큐를 이용해 최적해를 빠른 속도로 계산할 수 있는 동적계획법 문제이다.

 

동적계획법에 단조 큐를 활용하는 과정은 다음과 같다.

 

1. 먼저 덱에서 현재 징검다리로 건너올 수 없는 징검다리를 모두 제거한다.

 

2. 지역 최적해를 가진 이전 징검다리에서 현재 징검다리로 건너올 경우의 최적해를 계산한다. 현재 징검다리를 시작점으로 해서 가지는 점수나 이전 징검다리에서 가지고 있는 최적해 + 현재 징검다리를 밟았을 때 점수 둘 중 하나가 될 것이다.

 

3. 계산한 최적해와 최대 점수를 비교해서 저장한다.

#덱에는 이동할 수 있는 범위의 징검다리만 있으므로 계산한 최적해는 최댓값이 아닌 극댓값이라는 사실에 유의한다.

 

4. 현재 계산한 최적해보다 작은 값을 가지고 있는 이전 징검다리를 모두 제거한다. 이렇게 되면 덱에는 단조감소 관계에 있는 해를 가진 징검다리만 들어있게 된다.

 

전체 코드

#include <bits/stdc++.h>
     
using namespace std;
using ll = long long;
using pli = pair<ll, int>;
  
int n, d;
deque<pli> mono;
ll res = -1e18 - 5000;
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> n >> d;
 
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        while (mono.size() && mono.front().second < i - d)
            mono.pop_front();
        
        ll dp = x;
 
        if (mono.size())
            dp = max(dp, dp + mono.front().first);
        
        res = max(res, dp);
        
        while(mono.size() && mono.back().first <= dp)
            mono.pop_back();
        
        mono.push_back({dp, i});
    }
 
    cout << res;
}