<유사문제>
QUANTIZE https://algospot.com/judge/problem/read/QUANTIZE
1866 택배 https://www.acmicpc.net/problem/1866
2228 구간나누기 https://www.acmicpc.net/problem/2228
1. 재활용
N개의 일렬로 된 마을이 존재한다.
이 중에서 K개의 수집통을 놓을때 각 마을에서 가까운 수집통 까지의 거리의 합이
최소가 되는 거리의 합을 구하는 문제이다.
dp로 문제를 해결할 수 있다.
$DP[N][K]$ : N번째 마을까지 K개의 수집통을 놓을 때 거리의 합
$DP[N][K]$ = $min(DP[N][K], \sum_{t=1}^{N}(DP[N - t][K - 1] + dist[N-t][N]))$
여기서 $dist[from][to]$ : from에서 to까지 수집통 1개를 놓을 때 최소 거리의 합 이다.
수집통을 from에서 to까지 최소거리의 합을 만드는 수집통의 위치는 가운데라는것을 알 수 있다.
문제는 그 합을 구하는 것이다. $O(N^3)$으로 가운데 위치를 구해서 일일이 다 더해줄 수 있지만
$O(N^2)$방법이 있다.
수집통을 3에 놓았을 때 1에서 6까지 거리의 합을 구해보자.
우리가 구하고자하는것은 위의 표에서 초록색 선과 같다.
그리고 수집통을 기준으로 수집통포함 왼쪽을 $L$, 포함하지 않은 오른쪽을 $R$이라 하자.
여기서 $R-L$을 해보면 다음과 같은 그림이 나온다.
이것은 우리가 구하고자 했던 거리의 합에서 수집통의 거리가 중복되게 더해져있는 값이다. 이 중복값은 $L$의 개수 - $R$의 개수가 된다.
즉, $L$- $R$ +pos[mid]*(Lcnt - Rcnt)를 전처리로 구해놓으면 된다.
다음의 소스코드에서는 $O(N^3)$으로 푼 소스이다.
AC가 나오긴한다.
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define INF 987654321
vector<long long> arr;
vector<vector<long long>> dist;
vector<vector<long long>> dp;
int N, M;
void Init(){
for (int n = 0; n < N; n++)
for (int m = n+ 1; m < N; m++){
int mid = (n + m) / 2;
for (int k = n; k <= m; k++)
dist[n][m] += abs(arr[mid] - arr[k]);
}
}
long long getDistance(int lo, int hi){
return dist[lo][hi];
}
long long solve(int idx, int part){
long long &ret = dp[idx][part];
if (idx == N) return ret = 0;
if (part == 0) return ret = INF;
if (ret != -1) return ret;
ret = INF;
for (int plus = 1; idx + plus <= N; ++plus){
ret = min(ret, solve(idx + plus, part - 1) + getDistance(idx, idx + plus - 1));
}
return ret;
}
int main(){
setbuf(stdout, NULL);
int T;
scanf("%d", &T);
for (int t = 1; t <= T; t++){
scanf("%d%d", &N, &M);
arr = vector<long long>(N);
dp = vector<vector<long long>>(N + 1, vector<long long>(M + 1, -1));
dist = vector<vector<long long>>(N, vector<long long>(N, 0));
for (int n = 0; n < N; n++)
scanf("%lld", &arr[n]);
sort(arr.begin(), arr.end());
Init();
printf("Case #%d\n", t);
printf("%lld\n",solve(0, M));
}
return 0;
}
| c |
2. QUANTIZE
QUANTIZE문제도 위 문제랑 다름이 없다.
다만 거기서는 오차의 제곱의 최소합과 수집통을 한개 놓는다면 수집통의 위치에 꼭 있을 필요는 없다.
(종만북 참고)
(종만북 참고)
#include <cstdio>
#include <algorithm>
#include <vector>
#define INF 987654321
using namespace std;
int N, S;
vector<int> arr, sum, psum;
vector<vector<int>> dp;
int minerror(int lo, int hi){ //[lo,hi]구간 최소 error 반환
int s = lo == 0 ? sum[hi] : sum[hi] - sum[lo - 1];
int ps = lo == 0 ? psum[hi] : psum[hi] - psum[lo - 1];
int m = (int)(0.5 + (double)s / (hi - lo + 1));
return ps - 2 * m*s + m*m*(hi - lo + 1);
}
int solve(int idx, int quantize){
if (idx == N) return 0;
if (quantize == 0) return INF;
int &ret = dp[idx][quantize];
if (ret != -1) return ret;
ret = INF;
for (int plus = 1;idx + plus <= N; ++plus)
ret = min(ret, solve(idx + plus, quantize - 1) + minerror(idx, idx + plus - 1));
return ret;
}
int main(){
int T;
scanf("%d", &T);
while (T--){
scanf("%d%d", &N, &S);
arr = vector<int>(N);
sum = vector<int>(N);
psum = vector<int>(N);
dp = vector<vector<int>>(N, vector<int>(11, -1));
for (int n = 0; n < N; n++) scanf("%d", &arr[n]);
sort(arr.begin(), arr.end());
for (int n = 0; n < N; n++){
if (n == 0) sum[n] = arr[n], psum[n] = arr[n]*arr[n];
else sum[n] = sum[n - 1] + arr[n], psum[n] = psum[n - 1] + arr[n] * arr[n];
}
int ans = INF;
ans = min(ans,solve(0, S));
printf("%d\n", ans);
}
return 0;
}
| cs |
본점에서 지점으로 택배를 보내는데 두 가지 방법이 있다.
트럭으로 보내는 경우 거리와 물건 수에 비례해서 비용이 든다.
헬기로 보내는 경우 거리와 물건 수에 상관없이 특정 비용이 든다.
이 문제도 범위를 묶어 DP로 풀 수 있다.
글로 설명을 하기가 힘든것같다. 코드를 참고하길
(처음엔 점화식을 $dp[i][j]$로 2차원으로 설정했는데 $O(N^3)$으로 TLE가 나왔다.)
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int T, H; // 트럭, 헬기
int dp[3002];
int dist[3002][3002];
vector<int> obj;
void init() {
int limit = obj.size() - 1;
for (int n = 0;n <= limit;n++) {
dist[n][n] = 0;
for (int m = n + 1;m <= limit;m++) {
//n에서 m까지 거리의 합
dist[n][m] = (obj[m] - obj[n]) + dist[n][m - 1];
}
for (int m = n - 1;m >= 0;m--) {
dist[n][m] = (obj[n] - obj[m]) + dist[n][m + 1];
}
}
}
int truck(int r) {
return T * dist[0][r];
}
int helicopter(int l, int r) {
int mid = (l + r + 1) / 2;
return H + T * (dist[mid][l] + dist[mid][r]);
}
int solve(int right) {
if (right == 0) {
int t = T * obj[0];
return t < H ? t : H;
}
int &ret = dp[right];
if (ret != -1) return ret;
ret = min(truck(right), helicopter(0, right)); // [0,right]를 트럭으로만 간 거리, 헬기로만 간 거리
for (int middle = 0; middle < right; middle++) {
ret = min(ret, solve(middle) + helicopter(middle + 1, right));
}
return ret;
}
int main() {
memset(dp, -1, sizeof dp);
scanf("%d", &N);
for (int n = 0;n < N;n++) {
int spot;
scanf("%d", &spot);
obj.push_back(spot);
}
obj.push_back(0);
scanf("%d%d", &T, &H);
sort(obj.begin(), obj.end());
init();
int r = obj.size() - 1;
printf("%d\n", solve(r));
return 0;
}
| cs |
4. 구간 나누기
N이 작아서 처음에 $O(N^3)$으로 풀었는데도 통과됬다.
정확히 M개의 구간(한 구간은 연속된 수, 두 개의 구간은 붙으면 안됨)의 최대 합을 구하는 문제이다.
음수도 입력으로 들어오니 조심하자.
#include <cstdio>
#include <algorithm>
using namespace std;
#define IINF 987654321
#define INF (IINF / 2)
int N, M;
int sum[101];
int arr[101];
int dp[101][101];
void init(){
for (int n = 0; n < 101; n++)
for (int m = 0; m < 101; m++)
dp[n][m] = -IINF;
}
int solve(int part, int idx){ // idx까지 part로 구간을 나눌때 최대값
if (part == 0) return 0;
if (idx <= 0) return -INF;
int &ret = dp[part][idx];
if (ret != -IINF) return ret;
ret = -INF;
ret = max(ret, solve(part, idx - 1));
for (int next = idx; next >= 1; next--)
ret = max(ret, solve(part - 1, next - 2) + sum[idx] - sum[next - 1]);
return ret;
}
int main(){
init();
scanf("%d%d", &N, &M);
for (int n = 1; n <= N; n++)
scanf("%d", &arr[n]), sum[n] = sum[n - 1] + arr[n];
int ans;
ans = solve(M, N);
printf("%d\n", ans);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기