백준 13263 나무 자르기
23 Jun 2021https://www.acmicpc.net/problem/13263
나무들의 높이와 해당 나무를 다 자르고 난 후 충전 비용이 주어졌을 때 전기톱으로 나무를 자르는 가장 저렴한 방법 찾는 문제이다. 단 전기톱은 1번 사용시마다 충전해야하고 나무의 높이는 1만큼 감소한다. 마지막 나무의 충전 비용은 0이므로 사실상 마지막 나무를 가장 저렴하게 자르는 방법을 찾는 것과 같다. 이때 점화식은 다음과 같다.
dp[i] = min(b[j]*a[i] + dp[j])
딱 봐도 컨벡스헐 트릭 쓰는 문제로 보인다. 게다가 a는 증가수열이고 b는 감소수열이라고까지 조건을 제시해줬다. 다른건 앞에서 공부한 컨벡스 헐이랑 차이는 없지만 한가지 유의할 점으로는 a가 증가수열이기 때문에 lower bound로 직선을 찾을 필요가 없다는 것이다.
- query 함수
func query(x: Int) -> Int {
while ptr < stack.count-1 && stack[ptr+1].x < Double(x) {
ptr += 1
}
return stack[ptr].f(x)
}
코드를 보면 알 수 있듯이 ptr이라는 이전 선분이 위치한 index부터 1씩 증가시키면서 보면 된다. 초기값으로는 기울기 b[0], 절편 0으로 주고 시작하면 된다. 왜냐하면 충전이 되어있고 첫번째 나무의 길이는 항상 1이기 때문에 첫번째 나무를 자르는데 드는 비용은 0이 되기 때문이다.
- 전체 코드
struct line {
var a:Int
var b:Int
var x:Double
func f(_ xx: Int) -> Int {
return a*xx+b
}
}
let INF:Double = 1_000_000_007
var stack:[line] = []
var ptr = 0
func intersect(a: line, b: line) -> Double {
return Double(b.b-a.b)/Double(a.a-b.a)
}
func addLine(a: Int, b: Int) {
var tmp = line(a: a, b: b, x: -INF)
if stack.isEmpty {
stack.append(tmp)
return
}
while !stack.isEmpty {
let top = stack.last!
let x = intersect(a: top, b: tmp)
if x <= top.x {
stack.removeLast()
}
else {
break
}
}
tmp.x = intersect(a: stack.last!, b: tmp)
stack.append(tmp)
if ptr >= stack.count {
ptr = stack.count-1
}
}
func query(x: Int) -> Int {
while ptr < stack.count-1 && stack[ptr+1].x < Double(x) {
ptr += 1
}
return stack[ptr].f(x)
}
let n = Int(readLine()!)!
var a = readLine()!.split(separator: " ").map{Int(String($0))!}
var b = readLine()!.split(separator: " ").map{Int(String($0))!}
var dp = Array(repeating: 0, count: n)
addLine(a: b[0], b: dp[0])
for i in 1..<n {
dp[i] = query(x: a[i])
addLine(a: b[i], b: dp[i])
}
print(dp[n-1])