$N$개의 건물들의 좌표가 주어진다.
기지국은 정사각형의 중심에 설치하며 정사각형의 한변의 길이는 설치비용이 된다.
적절히 기지국을 설치하여 모든건물을 포함시킬 때 설치비용을 최소화하도록 하는 문제이다.
$N$이 10,000이 되어서 $O(N^2)$으로 해결 못할 줄 알았는데 2초내에는 해결이 된다고 한다.
top-down방식으로 풀었는데 dp를 2차원 배열에 저장시키다보니 런타임에러가 발생한다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N;
pair<int,int> bu[10001];
int dp[10001][10001];
int part[10001][10001][2]; //min, max
int solve(int l, int r) {
int &ret = dp[l][r];
if (ret != -1) return ret;
ret = max(bu[r].first - bu[l].first, max(part[l][r][0], part[l][r][1]) * 2);
for (int next = l;next < r;next++) {
int plus = max(bu[next].first - bu[l].first, max(part[l][next][1],part[l][next][0]) * 2);
ret = min(ret, solve(next + 1, r) + plus);
}
return ret;
}
int main() {
memset(dp, -1, sizeof dp);
scanf("%d", &N);
for (int n = 0;n < N;n++) scanf("%d%d", &bu[n].first, &bu[n].second);
sort(bu, bu + N);
for (int n = 0;n < N;n++) {
int mi = bu[n].second, ma = bu[n].second;
for (int m = n;m < N;m++) {
mi = min(mi, bu[m].second), ma = max(ma, bu[m].second);
if (n == m) part[n][m][0] = abs(bu[n].second), part[n][m][1] = abs(bu[n].second);
else part[n][m][0] = abs(mi), part[n][m][1] = abs(ma);
}
}
printf("%d\n", solve(0, N - 1));
return 0;
}
| cs |
그대로 logic을 유지하면서 bottom-up방식으로 해결해야한다.
$dp[n] = min_{m \in[n,0]}(dp[n], dp[m - 1] + max(h*2, x_{n}-x_{m}))$
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N;
pair<int,int> bu[10001];
int dp[10001];
int main() {
scanf("%d", &N);
for (int n = 0;n < N;n++) scanf("%d%d", &bu[n].first, &bu[n].second);
sort(bu, bu + N);
dp[0] = abs(bu[0].second) * 2;
for (int n = 1;n < N;n++) {
dp[n] = 0x3f3f3f3f;
int h = 0;
for (int m = n;m >= 0;m--) {
h = max(h, abs(bu[m].second));
dp[n] = min(dp[n], (m == 0 ? 0 : dp[m - 1]) + max(h * 2, bu[n].first - bu[m].first));
}
}
printf("%d\n", dp[N - 1]);
return 0;
}
| cs |
저거 O(nlogn)에 해결이 가능하다고 하더라고요..
답글삭제어떻게 해결해야 할지는 잘 모르겠지만요..
질문게시판에 있길래 봤는데 그냥 pass해버렸어요 ㅋㅋ
답글삭제