BOJ 19943 - 조명등
점화식
$dp[i]=i$ 번 째 조각품까지 밝힐 수 있는 조명등들을 달았을 때 최소 비용
이라고 하자.
또한, $C[i][j]=$ $i \le j \text{일 때, } [i, j]$ 구간의 조각품을 하나의 조명등으로 밝힐 수 있는 최소 비용이라고 하자.
$dp[i]=Min_{1 < j \le i-1 }\Bigl\{dp[j]+C[j+1][i]\Bigr\}$ 이다.
$C[i][j]$ 를 어떻게 구할 수 있을까?
$S_i=x_i-h_i~~E_i=x_i+h_i$ 라고 하자.
그럼 $C[i][j]=\Bigl({\dfrac {Max_{i \le k \le j}E_k-Min_{i \le k \le j}S_k}2}\Bigr)^2$ 이다.
이유는 다음과 같다.
$E_k$ 중 가장 큰 것을 $E’_k$ 라 하고, $S_k$ 중 가장 작은 것을 $S’_k$ 라 할 때,
어떤 조명등이든 $E’_k$ 를 만들어 낸 조각품을 밝히기 위해서는 $(E’_k, 0)$ 의 지점에서 동경 $135\degree$ 로 뻗어나가야 하고, 반대로 $S’_k$ 에선 $45\degree$ 로 뻗어나가야 한다.
그리고 이 두 직선이 만나는 교점이 바로 조명등이 설치가 되어야 할 지점이다.
$C[i][j]$ 에 대한 식을 세워도 어쨌든 $O(N^2)$ 짜리 DP일 뿐이다.
최적화
일반성을 잃지 않고 계산에 쓸모없는 조각품들을 삭제해보자.
우선 모든 조각품이 $S_i$ 의 오름차순으로 정렬되어있다고 하자.
$S_i \sim E_i$ 가 있을 때 $S_j \le S_i$이고 $E_j \ge E_i$ 인 $j,~(i \ne j)$ 가 있다면 $i$ 번 째 조각품은 쓸모없다.
이렇게 쓸모 있는 조각품들만 남기면 $C[i][j]$ 는 다음과 같다.
$C[i][j]=\Bigl({\dfrac {E_j-S_i}2}\Bigr)^2$
처음에 조각품들이 $S_i$ 로 정렬이 되어 있으므로 $S_i$ 가 $i \sim j$ 구간에서 가장 작은 $S$ 임을 알 수 있다.
$E_j$ 가 이전의 값들보다 더 큰 $E$ 값을 만들어내지 못했다면 제외가 되었을 것이므로 $E_j$ 는 저 구간에서 가장 큰 $E$ 값이 된다.
따라서,
$C[i][j]=1/4(E_j^2-2E_jS_i+S_i^2)$ 이다.
그럼 이제 $i$ 와 $j$ 에 대한 일차 다항식으로 표현이 되었으므로 CHT를 적용해서 문제를 $O(N \log N)$ 에 해결해줄 수 있다.
처음 식을 가져와보면,
$dp[1]=h_1^2$ 이다.
이제 문제를 해결할 수 있다.
이상하게 $X[i]$ 가 단조증가임에도 불구하고, 이분탐색을 써야 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