BOJ 13263 - 나무 자르기

문제 태그 : https://www.acmicpc.net/problem/13263

문제 소개

나무를 모두 자르고 싶다. 나무 N개의 길이$a_{i}$가 주어지고 N개의 $b_{i}$가 주어진다. 나무 길이 1을 자를때마다 다시 충전을 해야한다. 이때 충전하는 비용은 지금까지 완벽히 자른 나무의 번호 중 가장 큰 번호의 $b_{i}$이다.

이때 $a_{1}=1$ 이고, $b_{N}=0$ 이며, $a_{i}$는 증가하고 $b_{i}$는 감소한다.

문제 풀이

제일 중요한 사실은 $b_{N}=0$이라는 것이다. N번 나무를 자르면 그 이후로는 드는 비용이 0이기 때문에 이 문제를 다르게 해석하면 N번 나무를 자르는데 얼마나 비용이 드는가? 이다.

한 번에 N번 나무를 자를지 중간에 비용을 감소 시킨후 자르는 것이 좋은지 잘 판단을 해야한다. 당연히 N번 나무 이후에 다 공짜 이므로 그 전에는 $j<i$ 인 j에 대해서 i 이후에 j를 자를 이유는 없다.

$DP[i]$를 i까지 자르는데 드는 최소 비용으로 정의하자.
그러면 $DP[i]=\underset{j<i}{min}(b_{j}*a_{i}+DP[j])$ 라는 식이 나온다. 
N의 제한은 100000이므로 $O(N^2)$의 시간복잡도로는 해결할 수 없고 따라서 CHT를 이용해야 한다. 
(CHT를 모른다면 이 글을 보고 오자.)

$ax+b$의 직선으로 만들어진 볼록껍질에서 x에 $a_{i}$를 넣어 $DP[i]$를 구하고 다시 $a=b_{i}$, $b=DP[i]$인 직선을 넣어가면서 볼록껍질을 조금씩 업데이트 해주면 된다.

※ 마지막은 충전을 안해도 됨으로 자르기 직전에 충전을 한다고 생각하자.
그러면 첫 나무의 길이는 1이므로 DP[1]은 항상 0이 될 것이고, $y=b_{1}x$ 의 직선이 항상 맨 처음에 들어갈 것이다.

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
#define ff first
#define ss second
 
struct lin{ 
    ll a,b;
};
 
ll sz=0;
lin stk[1010101];
double cx(ll a,ll b) {
    return 1.0 * (double)(stk[a].b - stk[b].b) / (stk[b].a - stk[a].a);
}
void insert(lin v){
    stk[sz] = v;
    while(1<sz&&cx(sz-2,sz-1)>cx(sz-1,sz)){
        stk[sz-1] = stk[sz];
        sz--;
    }
    sz++;
}
ll sol(ll x){ 
    ll lo=0,hi=sz-1;
    while(lo<hi){
        ll mid=(lo+hi)/2;
        if (cx(mid,mid+1)<=x) lo=mid+1;
        else hi=mid;
    }
    return stk[lo].a*x+stk[lo].b;
}
void clear(){
    sz=0;
}
 
ll arr[1010101];
ll brr[1010101];
ll dp[1010101];
 
int main(){
    ll i,j,k,m,n;
    scanf("%lld",&n);
    for(i=1;i<=n;i++)
        scanf("%lld",&arr[i]);
    for(i=1;i<=n;i++)
        scanf("%lld",&brr[i]);
    
    lin l;
    l.a = brr[1];
    l.b = 0;
    insert(l);
    for(i=2;i<=n;i++){
        dp[i]=sol(arr[i]);
        l.a = brr[i];
        l.b = dp[i];
        insert(l);
    }
    printf("%lld",dp[n]);
    return 0;
}