(5977) Mowing the Lawn

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

단계별로 풀어보기

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

 

 

 

수열 중 일부를 선택했을 때 최대값을 찾는 문제. 단 연속해서 k개를 초과하여 선택할 수 없다.

수열의 전체 합은 일정하므로 선택한 값이 최대가 된다는 것은 선택하지 않은 값이 최소가 된다는 것이다.

다시 말해 간격이 k+1개 이하가 되도록 선택했을 때 최소값을 찾는 문제와 동치이다.

dp[x]를 x번 소를 선택했고 조건을 만족시키는 최소값으로 정의하자. 이때 dp의 점화식은 아래와 같다.

dp[0]= 0: 소를 선택하지 않으면 최소값은 0이다.

(1≤x≤k+1)  dp[x]= v[x]: x번 소를 선택했다면 1번~x-1번 소는 선택하지 않아도 조건을 만족한다.

(k+1<x≤N) dp[x]= v[x]+min(dp[y])(x-k-1≤y≤x-1): x-k-1~x-1번 소 중 하나를 선택해야 조건을 만족하므로 구간 내 dp값 중 최소값을 더해야 한다.

여기서 min(dp[y])를 덱 최대값 트릭을 이용해 빠르게 구하면 된다.

조건을 만족하려면 n-k~n번 소 중 하나를 선택해야 하므로 DP값 갱신이 끝난 뒤 dp[n-k]~dp[n]중 최소값(dp[0]=0으로 n=k일 때 예외처리도 되어있음)을 찾아 전체 총합에서 빼주면 된다.

사실 dp[n-k]~dp[n]는 탐색 과정에서 덱에서 정렬되었으므로 따로 찾을 필요 없이 덱 맨 앞을 가져오면 되는데, 대신 이때는 n=k 예외처리를 해줘야 한다.

 

 

 

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, k;
  long tot= 0, res= 100000000000000;
  
  cin >> n >> k;
  
  vector<int> v(n+1);
  vector<long> dp(n+1);
  
  for(int i=1;i<=n;i++){
    cin >> v[i];
    tot+= v[i];
  }
  
  deque<int> dq;
  
  for(int i=1;i<=n;i++){
    dp[i]= (i<=k+1 ? v[i] : dp[dq.front()]+v[i]);
    
    while(!dq.empty() && dp[dq.back()]>dp[i])  dq.pop_back();
    
    dq.push_back(i);
    
    while(dq.front()<i-k)  dq.pop_front();
  }
  
  for(int i=n-k;i<=n;i++)  res= min(res, dp[i]);
  
  // cout << tot-dp[dq.front()];로 해도 n!=k일 때 성립함
  cout << tot-res;
  
  return 0;
}

 

 

 

그리고 중요하진 않지만 DP 갱신에 필요한 데이터는 덱에 들어있기 때문에 굳이 DP배열를 선언하지 않을 수 있다.

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, k;
  long tot= 0;
  
  cin >> n >> k;
  
  deque<pair<long,int>> dq;
  
  for(int i=0;i<n;i++){
    int e;
    
    cin >> e;
    
    long val= (i<k+1 ? e : dq.front().first+e);
    tot+= e;
    
    while(!dq.empty() && dq.back().first>val)  dq.pop_back();
    
    dq.push_back({val,i});
    
    while(dq.front().second<i-k)  dq.pop_front();
  }
  
  cout << tot-(n==k ? 0 : dq.front().first);
  
  return 0;
}