BOJ 19943 - 조명등
점화식Permalink
번 째 조각품까지 밝힐 수 있는 조명등들을 달았을 때 최소 비용
이라고 하자.
또한, 구간의 조각품을 하나의 조명등으로 밝힐 수 있는 최소 비용이라고 하자.
이다.
를 어떻게 구할 수 있을까?
라고 하자.
그럼 이다.
이유는 다음과 같다.
중 가장 큰 것을 라 하고, 중 가장 작은 것을 라 할 때,
어떤 조명등이든 를 만들어 낸 조각품을 밝히기 위해서는 의 지점에서 동경 로 뻗어나가야 하고, 반대로 에선 로 뻗어나가야 한다.
그리고 이 두 직선이 만나는 교점이 바로 조명등이 설치가 되어야 할 지점이다.
에 대한 식을 세워도 어쨌든 짜리 DP일 뿐이다.
최적화Permalink
일반성을 잃지 않고 계산에 쓸모없는 조각품들을 삭제해보자.
우선 모든 조각품이 의 오름차순으로 정렬되어있다고 하자.
가 있을 때 이고 인 가 있다면 번 째 조각품은 쓸모없다.
이렇게 쓸모 있는 조각품들만 남기면 는 다음과 같다.
처음에 조각품들이 로 정렬이 되어 있으므로 가 구간에서 가장 작은 임을 알 수 있다.
가 이전의 값들보다 더 큰 값을 만들어내지 못했다면 제외가 되었을 것이므로 는 저 구간에서 가장 큰 값이 된다.
따라서,
이다.
그럼 이제 와 에 대한 일차 다항식으로 표현이 되었으므로 CHT를 적용해서 문제를 에 해결해줄 수 있다.
처음 식을 가져와보면,
이다.
이제 문제를 해결할 수 있다.
이상하게 가 단조증가임에도 불구하고, 이분탐색을 써야 AC가 나왔다.
const int inf = 2e34;
struct line {
mutable int m, k;
double p;
double cross(const line &o) {
return 1.0 * (o.k - k) / (m - o.m);
}
};
void solve() {
int n;
cin >> n;
debug(signed(n));
vector<pi> a(n);
for (auto &[x, h]: a) {
cin >> x >> h;
x *= 2;
h *= 2;
}
sort(all(a), [&](auto &a, auto &b) {
int ea = a.fi + a.se, eb = b.fi + b.se;
int sa = a.fi - a.se, sb = b.fi - b.se;
if (sa != sb) return sa < sb;
return ea > eb;
});
vi s;
vector<pi> new_a;
for (int i = 0; i < n; i++) {
if (sz(s) && s.back() >= a[i].fi + a[i].se) continue;
s.pb(a[i].fi + a[i].se);
new_a.pb(a[i]);
}
a = new_a;
n = sz(a);
vector<int> dp(n), S(n), E(n);
for (int i = 0; i < n; i++) {
S[i] = a[i].fi - a[i].se;
E[i] = a[i].fi + a[i].se;
}
auto m = [&](int i) {
return -S[i + 1] / 2;
};
auto k = [&](int i) {
return S[i + 1] * S[i + 1] / 4 + dp[i];
};
auto x = [&](int i) {
return E[i];
};
dp[0] = a[0].se * a[0].se;
vector<line> lines;
if (n > 1)
lines.pb({m(0), k(0), -inf});
for (int i = 1, j = 0; i < n; i++) {
dp[i] = (E[i] - S[0]) * (E[i] - S[0]) / 4;
int lo = 0, hi = sz(lines) - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (lines[mid].p <= x(i)) {
j = mid;
lo = mid + 1;
} else hi = mid - 1;
}
//while (j < sz(lines) - 1 && lines[j + 1].p <= x(i)) j++;
int c = E[i] * E[i] / 4;
dp[i] = min(dp[i], lines[j].m * x(i) + lines[j].k + c);
if (i < n - 1) {
line new_line = {m(i), k(i)};
while (sz(lines) > 1) {
new_line.p = new_line.cross(lines.back());
if (new_line.p <= lines.back().p) {
lines.pop_back();
} else {
break;
}
}
assert(sz(lines));
new_line.p = new_line.cross(lines.back());
lines.pb(new_line);
}
}
assert(dp[n - 1] > 0);
cout << dp[n - 1] / 4;
if (dp[n - 1] % 4 == 0) cout << ".00";
else if (dp[n - 1] % 4 == 1) cout << ".25";
else if (dp[n - 1] % 4 == 3) cout << ".75";
else cout << ".50";
cout << endl;
}
Comments