문제 링크
- http://icpc.me/13263
사용 알고리즘
- Convex Hull Trick
- DP
시간복잡도
- O(n)
풀이
CHT를 모르신다면 (이 글)을 먼저 읽고 와주시기 바랍니다.
먼저 점화식을 세워본다면 dp[i] = min(dp[j] + b[j] * a[i])이고, ai는 증가하고 bi는 감소한다고 문제에 써있기 때문에 CHT라는 것을 알 수 있습니다.
CHT를 적용하여 문제를 해결합시다.
전체 코드
https://github.com/justiceHui/BOJ/blob/master/13263.cpp