BOJ 5060 - 무글 맵스
DP 문제이고 다음과 같이 Cost 함수를 전처리해두자.
와 에 집이 설치되었을 때, 인 들에 대해 번 째 집들의 오차의 합
이는 로 전처리 가능하다.
이제 함수를 정의한다.
번째 집에 마지막 집을 짓고 개의 집을 지었을 때 최소 오차 합
는 에 채울 수 있고, 마지막에 이 정답이 된다.
그 이유는 우리가 구한건 집들의 오차의 합인데, 오차의 평균을 구해야 하기 때문이다.
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;
}
Comments