13263번: 나무 자르기 - DP(컨벡스 헐 트릭)

컨벡스 헐 트릭 기본 문제.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

const int MAXN = 100001;
struct line
{
    ll gra, yi; //gra : 기울기, yi : y절편
    ld x = 0.0; //해당 직선이 시작하는 x좌표
    bool operator<(line l) { return x < l.x; }
};
int n;
ll a[MAXN]; //나무의 길이. x좌표를 의미한다.
ll b[MAXN]; //전기톱의 충전량. 기울기를 의미한다.
ll dp[MAXN]; //dp[i]: i번째 나무를 자를 때의 최솟값. y절편을 의미한다.
vector<line> CHT;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> n;
	for(int i=1; i<=n; i++) cin >> a[i]; 
	for(int i=1; i<=n; i++) cin >> b[i]; 
	
	CHT.push_back({b[1], 0, 0.0}); //첫 번째 나무를 자르는 값은 0이다(dp[1] = 0). 일차함수 역시 y=b[1]*x가 된다.
	for(int i=2; i<=n; i++)
	{
	    //이분 탐색으로 a[i] 길이만큼의 나무를 자를 때 어떤 직선을 택해야 하는지 탐색한다.
	    //lower_bound는 a[i]보다 더 큰 시작점을 구하기 때문에 prev를 이용한다.
	    line tmp = {0, 0, (ld)a[i]};
	    line res = *prev(lower_bound(CHT.begin(), CHT.end(), tmp));
	    dp[i] = res.gra * a[i] + res.yi; //찾은 직선에 a[i]를 대입해 dp[i]를 구한다.
	    
	    line next = {b[i], dp[i], 0.0}; //다음 직선은 기울기가 b[i], y절편이 dp[i]가 된다.
	    while(true)
	    {
	        line prev = CHT.back();
	        ld px = (ld)(prev.yi - next.yi) / (next.gra - prev.gra);
	        //px : 지금 만든 직선과 이전에 만든 직선의 교점의 x좌표
	        
	        if(px <= prev.x) //px가 더 작으면 이전에 만든 직선을 유지할 이유가 없다.
	        {
	            CHT.pop_back();
	            continue;
	        }
	        
	        next.x = px;
	        CHT.push_back(next);
	        break;
	    }
	}
	
	cout << dp[n];
}