[백준] 13263 나무 자르기 - C++

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

---

$DP[i]$ : $i$번째 나무를 높이가 1이 되게 하는 최소비용 이다.

그럼 점화식이 $DP[i] = min( A[i] * B[j] + DP[j] )\;(0\le j < i )$ 임을 알 수 있다.

이때 $A[i] * B[j]$는 $i$보다 작은 $j$에 대해, $i$번째 나무를 $j$번째 비용으로 모두 자른다는 뜻이고,

$DP[j]$는 $j$번째 비용을 사용하기 위해 $j$번째 나무를 자르는걸 의미한다.

 

하지만 n이 100,000이라 $O(n^{2})$은 안되기 때문에....

CHT를 써줘야 한다!

문제 조건에 의해 $a_{i}$는 단조증가하고, $b_{i}$는 단조감소하기 때문에, CHT를 쓸 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;

struct Line {
	ll m, b; //기울기, y절편
	db start; //스타트포인트 (반직선형태)
};

db cross(Line& a, Line& b) { //두 직선의 교점의 x좌표를 구하는 함수
	return (db)(a.b - b.b) / (db)(b.m - a.m);
}

int main() {
	int n;
	cin >> n;
	vector<ll> va(n), vb(n), dp(n);
	for (int i = 0; i < n; i++) {
		cin >> va[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> vb[i];
	}
	vector<Line>hull; //직선을 담을 컨테이너
    
	for (int i = 1; i < n; i++) {
    
		Line l = { vb[i - 1], dp[i - 1], 0 }; //새로운 직선 정의
		while (!hull.empty()) { //가장 최근 직선과의 교점을 보고, 새로운 직선에 의해 쓸모없어지는 기존 직선을 삭제.
			l.start = cross(hull.back(), l);
			if (hull.back().start < l.start) {
				break;
			}
			hull.pop_back();
		}
		hull.push_back(l);

		ll x = va[i]; //함숫값을 구하려는 x좌표

		//이분탐색을 통해 함숫값을 구하려는 x좌표가 포함된 구간을 담당하는 직선을 찾음
		int pos = hull.size() - 1; //res
		if (x < hull.back().start) {
			int left = 0;
			int right = hull.size() - 1;
			while (left + 1 < right) {
				int mid = (left + right) / 2;
				if (x < hull[mid].start) {
					right = mid;
				}
				else {
					left = mid;
				}
			}
			pos = left;
		}
		dp[i] = hull[pos].m * x + hull[pos].b;
	}
	cout << dp[n-1];
	return 0;
}

 

설명은 주석에 달아두었다.

---

생각보다는 직관적인 것 같다..

https://blog.naver.com/kks227/221418495037

이 블로그를 참고하였다.

---