(13263) 나무 자르기

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

단계별로 풀어보기

62단계(동적 계획법 최적화 1) 2번째

 

 

 

컨벡스 헐을 사용할 수 있는 점화식의 형태는 다음과 같다.

dp[i]= min(dp[j] + b[j]*a[i]) (j < i), b[j] ≥ b[j+1]

이때 min부분을 전부 순회하면 O(N^2)가 걸리는 계산을 O(N log N)으로 줄일 수 있으며, a[i] ≤ a[i+1]이라면 O(N)까지도 줄일 수 있다. 위 점화식에서 a[i]를 x로 두면 f(x)=b[j]x+dp[j] 형태의 일차함수로 나타낼 수 있고, 이 일차함수에서 최소값을 구하는 문제가 된다. 이 최소값을 이전 문제의 방식으로 최소값이 되는 j와 그 범위를 저장하면 이분 탐색을 통해 O(log N)으로 dp[i]를 구할 수 있다. a[i] ≤ a[i+1]라면 x좌표가 계속 증가하므로 이전 선분을 볼 필요가 없어서 이분 탐색 대신 스위핑을 이용하여 거의 O(1)에 dp[i]를 구할 수 있다.

이 문제는 기초 형태라 위 점화식을 그대로 이용하면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
typedef pair<pair<long,long>,double> LF_t; // Linear Function ax+b(x>=c)

inline double cross(LF_t f1, LF_t f2){
  return static_cast<double>(f2.first.second-f1.first.second)/(f1.first.first-f2.first.first);
}

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<int> a(n+1), b(n+1);
  vector<long> dp(n+1);
  vector<LF_t> f;
  
  for(int i=1;i<=n;i++)  cin >> a[i];
  for(int i=1;i<=n;i++)  cin >> b[i];
  
  for(int i=2;i<=n;i++){
    LF_t now= {{b[i-1], dp[i-1]}, 0.0f};
    
    while(!f.empty()){
      now.second= cross(f.back(), now);
      
      if(f.back().second<now.second) break;
      
      f.pop_back();
    }
    
    f.push_back(now);
    
    int lo= 0, hi= f.size();
    while(lo+1<hi){
      int mid= (lo+hi)/2;
      
      (a[i]<f[mid].second ? hi:lo)= mid;
    }
    
    dp[i]= a[i] * f[lo].first.first + f[lo].first.second;
  }
  
  cout << dp[n];
  
  return 0;
}

 

 

 

j를 이분탐색 대신 스위핑으로 찾는 코드. 보면 알겠지만 완전 O(1)은 아니고, DP를 N번 돌리면서 총 N번 탐색하는 거라 amortized O(1)이다.

  for(int i=2, fpos=0;i<=n;i++){
    LF_t now= {{b[i-1], dp[i-1]}, 0.0f};
    
    while(!f.empty()){
      now.second= cross(f.back(), now);
      
      if(f.back().second<now.second) break;
      
      f.pop_back();
      fpos= min<int>(fpos, f.size()-1);
    }
    
    f.push_back(now);
    
    while(fpos+1<f.size() && f[fpos+1].second<a[i]) fpos++;
    
    dp[i]= a[i] * f[fpos].first.first + f[fpos].first.second;
  }