문제링크
https://www.acmicpc.net/problem/6171
6171번: 땅따먹기
(1) / (4) / (2, 3) 으로 땅을 묶어 사보자. 상헌이는 100 * 1 + 20 * 15 + 1 * 100 = 500의 가격에 땅을 살 수 있다.
www.acmicpc.net
풀이
- 자신의 w, h 보다 모두 큰 땅이 존재하면 그 땅은 그 큰 땅에 포함하여 사면 비용을 들이지 않고 사기 가능
- 그러한 땅들을 모두 제외하면 w 오름차순으로 정렬했을 때 h 는 내림차순으로 정렬됨
- i 번 땅과 j 번 땅을 같이 묶어서 사면, 그 사이에 있는 땅들은 포함해도 추가 비용 들지 않음
- i번 땅과 묶인 땅들의 비용 = w[i] * h[j] 이므로
- 따라서, $dp[i]:$ i 번 땅까지 사는데 필요한 최소 비용이라고 정의하면
- $dp[i] = min_{0 \leq j < i} (dp[j] + w[i] * h[j + 1]) $
- CHT 적용
- x: 증가
- 기울기: 감소
- getMin
- CHT 적용
코드
- 시간복잡도: $O(N)$
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
struct line {
long long m, c;
long long eval(long long x) {return m * x + c;}
long long intersecX(line l) {return (c - l.c) / (l.m - m);}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
vector<pair<long long, long long> > v(N);
for (int i = 0; i < N; ++i) {
cin >> v[i].first >> v[i].second;
}
sort(all(v));
vector<pair<long long, long long> > v2;
long long prevMax = v.back().second;
v2.push_back(v.back());
for (int i = N - 2; i >= 0; --i) {
if (v[i].second > prevMax) {
v2.push_back(v[i]);
prevMax = v[i].second;
}
}
reverse(all(v2));
deque<line> dq;
long long ans = 0;
dq.push_back({v2[0].second, 0});
for (int i = 0; i < v2.size(); ++i) {
while (dq.size() >= 2 && dq[0].eval(v2[i].first) >= dq[1].eval(v2[i].first)) dq.pop_front();
ans = dq.front().eval(v2[i].first);
ans = dq.front().eval(v2[i].first);
if (i == v2.size() - 1) break;
line cur = {v2[i + 1].second, ans};
while (dq.size() >= 2 && cur.intersecX(dq.back()) <= dq.back().intersecX(dq[dq.size() - 2])) dq.pop_back();
dq.push_back(cur);
}
cout << ans << '\n';
}728x90
'PS > BOJ' 카테고리의 다른 글
| 백준 2011번: 암호코드 (0) | 2022.07.02 |
|---|---|
| 백준 13546번: 수열과 쿼리 4 (0) | 2022.03.08 |
| 백준 3295번: 단방향 링크 네트워크 (0) | 2022.03.07 |
| 백준 1605번: 반복 부분문자열 (0) | 2022.03.07 |
| 백준 11479번: 서로 다른 부분 문자열의 개수 2 (0) | 2022.03.07 |