(33918) 맛있는 스콘 만들기

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

단계별로 풀어보기

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

 

 

 

여기까지 왔을 정도면 PS 경험치가 충분히 쌓였을테니 제한을 보고 추측할 수 있다.

덱 최대값 테크닉은 보통 O(N)이었는데, 여기서 N이나 M의 범위가 그것보다 작다. 따라서 O(NM)이라고 눈치껏 알아낼 수 있다.

문제가 어려워지면 어떤 알고리즘을 써야 할지부터 막막해지기 때문에 이렇게 제한 범위를 보며 가능한 해답의 시간 복잡도를 추측하는 것은 실제로 도움이 된다.

 

dp[k][x]를 시각 k-1에 온도를 x로 맞췄을 때 맛의 최대값이라고 하자.

이때 dp[k][x]= f(k,x)+max(dp[k-1][y])이다. f(k,x)는 문제에서 설명한 대로 M-|b(k-1)-x|이고 max(dp[k-1][y])는 덱 최대값 테크닉으로 구하면 된다.

이 과정을 시각 0부터 N-1까지, 온도 1부터 M까지 순회하며 DP를 갱신하면 된다.

단 주의할 점이 두 가지가 있다.

온도를 C의 정수배만큼 조절할 수 있으므로, 온도를 순회할 때 1,1+C,1+2C, ... ,(초기화)2,2+C,2+2C, ... ,(초기화)3, ... 이런 식으로 순회해야 한다.

또 x를 갱신하기 위해 탐색해야 하는 y의 가능한 범위는 x-d부터 x+d까지이므로 이를 고려해 갱신 시기를 잘 설정해야 한다.

 

이 문제도 dp[k]라인을 갱신할 때 dp[k-1]라인만 있으면 되므로 메모리를 줄일 수 있다.

 

 

 

#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, m, c, d;
  
  cin >> n >> m >> c >> d;
  
  vector<int> v(n);
  vector dp(2, vector<int> (m+1));
  deque<int> dq;
  
  for(int i=0;i<n;i++)  cin >> v[i];
  
  for(int i=1;i<=m;i++)  dp[0][i]= m-abs(v[0]-i);
  
  for(int i=1;i<n;i++){
    for(int j=1;j<c+1;j++){
      dq.clear();
      
      for(int t=j;t<=m+d;t+=c){
        while(!dq.empty() && t<=m && dp[0][dq.back()]<dp[0][t])  dq.pop_back();
        
        if(t<=m)  dq.push_back(t);
        
        while(dq.front()<t-2*d)  dq.pop_front();
        
        if(1<=t-d)  dp[1][t-d]= dp[0][dq.front()]+m-abs(v[i]-(t-d));
      }
    }
    
    dp[0]= dp[1];
  }
  
  cout << *max_element(dp[0].begin()+1, dp[0].end());
  
  return 0;
}