BOJ 5060 - 무글 맵스

BOJ 5060 - 무글 맵스

DP 문제이고 다음과 같이 Cost 함수를 전처리해두자.

$\text{cost}[a][b]=$ $a$와 $b$에 집이 설치되었을 때, $a < k < b$ 인 $k$ 들에 대해 $k$번 째 집들의 오차의 합

이는 $O(n^2)$ 로 전처리 가능하다.

이제 $dp$ 함수를 정의한다.

$dp[i][j]=$ $i$ 번째 집에 마지막 집을 짓고 $j$ 개의 집을 지었을 때 최소 오차 합

$dp$는 $O(n^3)$ 에 채울 수 있고, 마지막에 $\dfrac{dp[h][c]}h$ 이 정답이 된다.

그 이유는 우리가 구한건 집들의 오차의 합인데, 오차의 평균을 구해야 하기 때문이다.

double dp[201][201], cost[201][201];
int h, c;
vi x;

void solve() {
   debug(dp[0][0]);
   cin >> h >> c;
   x = vi(h);
   fv(x);
   sort(all(x));

   for (int i = 0; i < h; i++) {
      for (int j = i + 1; j < h; j++) {
         cost[i][j] = 0;
         for (int k = i + 1; k < j; k++) {
            cost[i][j] += abs(x[k] - (x[i] + 1.0 * (x[j] - x[i]) * (1.0 * (k - i) / (j - i))));
         }
      }
   }

   // 집 인덱스
   for (int i = 0; i < h; i++) for (int c = 0; c <= h; c++) dp[i][c] = 2e15;
   dp[0][1] = 0;
   dp[0][0] = 0;
   for (int i = 1; i < h; i++) {
      // 지금까지 집을 몇개 저장했는지
      for (int j = 2; j <= min(c, i + 1); j++) {
         dp[i][j] = 2e15;
         // 마지막으로 저장한 집
         debug(i, j);
         for (int k = i - 1; k >= j - 2; k--) {
            dp[i][j] = min(dp[i][j], dp[k][j - 1] + cost[k][i]);
            debug(dp[i][j]);
         }
      }
   }
   cout << setprecision(4) << fixed << dp[h - 1][c] / h << endl;
}