(15678) 연세워터파크

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

단계별로 풀어보기

38단계(스택, 큐, 덱 2) 8번째

 

 

 

밟는 순서는 상관 없으므로 낮은 인덱스부터 오름차순으로 밟아간다고 생각한다.

dp[x]를 마지막으로 x번 징검다리를 밟았을 때 점수의 최대값이라고 하자.

x-d~x-1번 징검다리에서 x번 징검다리로 올 수 있으므로 dp[x]=v[x]+max(dp[y]) (max(1,x-d)≤y≤x-1)이다.

마찬가지로 max(dp[y])를 덱 최대값 트릭을 이용해 구하면 된다.

단 max(dp[y])<0이라면 건너오는 게 손해이므로 dp[x]=v[x]이다. (x번 징검다리를 시작점으로 한다는 의미)

갱신이 끝난 뒤 dp[1]~dp[n] 중 최댓값이 정답이다.

 

 

 

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, d;
  
  cin >> n >> d;
  
  vector<int> v(n);
  vector<long> dp(n);
  
  for(int i=0;i<n;i++)  cin >> v[i];
  
  deque<int> dq;
  
  dq.push_back(0);
  dp[0]= v[0];
  
  for(int i=1;i<n;i++){
    dp[i]= max(dp[dq.front()],0L)+v[i];
    
    while(!dq.empty() && dp[dq.back()]<dp[i])  dq.pop_back();
    
    dq.push_back(i);
    
    while(dq.front()<i-d+1)  dq.pop_front();
  }
  
  cout << *max_element(dp.begin(), dp.end());
  
  return 0;
}