| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1148004 | abel | Coin Collecting (JOI19_ho_t4) | Java | 0 ms | 0 KiB |
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public Main {
static int totalCoins;
static final long INF = (long) 1e18;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
totalCoins = Integer.parseInt(reader.readLine().trim());
List<int[]> positions = new ArrayList<>();
for (int i = 0; i < 2 * totalCoins; i++) {
String[] input = reader.readLine().trim().split(" ");
positions.add(new int[] {
Integer.parseInt(input[0]),
Integer.parseInt(input[1])
});
}
if (totalCoins <= 20) {
System.out.println(dpMemoization(positions));
} else {
greedyCount(positions);
}
}
static long dpMemoization(List<int[]> positions) {
Map<String, Long> memo = new HashMap<>();
return dpHelper(positions, new boolean[2 * totalCoins], 1, memo);
}
static long dpHelper(List<int[]> positions, boolean[] used, int placedCoins, Map<String, Long> memo) {
if (placedCoins > 2 * totalCoins) {
return 0;
}
String key = generateKey(used, placedCoins);
if (memo.containsKey(key)) {
return memo.get(key);
}
long minCost = INF;
for (int i = 0; i < 2 * totalCoins; i++) {
if (!used[i]) {
used[i] = true;
int[] coinPosition = positions.get(i);
long moveCost;
if (placedCoins > totalCoins) {
moveCost = Math.abs(coinPosition[0] - (placedCoins - totalCoins))
+ Math.abs(coinPosition[1] - 2);
} else {
moveCost = Math.abs(coinPosition[0] - placedCoins)
+ Math.abs(coinPosition[1] - 1);
}
long totalCost = moveCost + dpHelper(positions, used, placedCoins + 1, memo);
minCost = Math.min(minCost, totalCost);
used[i] = false;
}
}
memo.put(key, minCost);
return minCost;
}
static String generateKey(boolean[] used, int placedCoins) {
StringBuilder sb = new StringBuilder();
for (boolean b : used) {
sb.append(b ? '1' : '0');
}
sb.append(placedCoins);
return sb.toString();
}
static void greedyCount(List<int[]> positions) {
int[][] targetCounts = new int[totalCoins + 1][2];
long movesCount = 0;
for (int[] coinPosition : positions) {
int x = coinPosition[0], y = coinPosition[1];
if (x < 1) {
movesCount += (1 - x);
x = 1;
} else if (x > totalCoins) {
movesCount += (x - totalCoins);
x = totalCoins;
}
if (y < 1) {
movesCount += (1 - y);
y = 1;
} else if (y > 2) {
movesCount += (y - 2);
y = 2;
}
targetCounts[x][y - 1]++;
}
for (int i = 1; i <= totalCoins; i++) {
targetCounts[i][0] += targetCounts[i - 1][0] - 1;
targetCounts[i][1] += targetCounts[i - 1][1] - 1;
if (targetCounts[i][0] > 0 && targetCounts[i][1] < 0) {
int movesNeeded = Math.min(targetCounts[i][0], -targetCounts[i][1]);
movesCount += movesNeeded;
targetCounts[i][0] -= movesNeeded;
targetCounts[i][1] += movesNeeded;
}
movesCount += Math.abs(targetCounts[i][0]) + Math.abs(targetCounts[i][1]);
}
System.out.println(movesCount);
}
}