BOJ 19943 - 조명등

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)$ 에 해결해줄 수 있다.

처음 식을 가져와보면,

$$ \begin{aligned} dp[i] =\left( \dfrac {E_i^2}{4}- \dfrac {S_{j+1}}{2} E_i+ \dfrac {S_{j+1}^2}{4} + dp[j] \right) \end{aligned} $$

$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;  
}